{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T09:25:50Z","timestamp":1791019550143,"version":"4.1.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,11]]},"abstract":"<jats:p>\n            Top-\n            <jats:italic>k<\/jats:italic>\n            spatial preference queries return a ranked set of the\n            <jats:italic>k<\/jats:italic>\n            best data objects based on the scores of feature objects in their spatial neighborhood. Despite the wide range of location-based applications that rely on spatial preference queries, existing algorithms incur non-negligible processing cost resulting in high response time. The reason is that computing the score of a data object requires examining its spatial neighborhood to find the feature object with highest score. In this paper, we propose a novel technique to speed up the performance of top-k spatial preference queries. To this end, we propose a mapping of pairs of data and feature objects to a distance-score space, which in turn allows us to identify and materialize the minimal subset of pairs that is sufficient to answer any spatial preference query. Furthermore, we present a novel algorithm that improves query processing performance by avoiding examining the spatial neighborhood of the data objects during query execution. In addition, we propose an efficient algorithm for materialization and we describe useful properties that reduce the cost of maintenance. We show through extensive experiments that our approach significantly reduces the number of I\/Os and execution time compared to the state-of-the-art algorithms for different setups.\n          <\/jats:p>","DOI":"10.14778\/1921071.1921076","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"93-104","source":"Crossref","is-referenced-by-count":39,"title":["Efficient processing of top-k spatial preference queries"],"prefix":"10.14778","volume":"4","author":[{"given":"Jo\u00e3o B.","family":"Rocha-Junior","sequence":"first","affiliation":[{"name":"Norwegian University of Science and Technology (NTNU), Trondheim, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Akrivi","family":"Vlachou","sequence":"additional","affiliation":[{"name":"Norwegian University of Science and Technology (NTNU), Trondheim, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Doulkeridis","sequence":"additional","affiliation":[{"name":"Norwegian University of Science and Technology (NTNU), Trondheim, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kjetil","family":"N\u00f8rv\u00e5g","sequence":"additional","affiliation":[{"name":"Norwegian University of Science and Technology (NTNU), Trondheim, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,11]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"156","volume-title":"Proc. of Int. Conf. on Data Engineering (ICDE)","author":"B\u00f6hm C.","year":"2007","unstructured":"C. B\u00f6hm , B. C. Ooi , C. Plant , and Y. Yan . Efficiently processing continuous k-nn queries on data streams . In Proc. of Int. Conf. on Data Engineering (ICDE) , pages 156 -- 165 , 2007 . C. B\u00f6hm, B. C. Ooi, C. Plant, and Y. Yan. Efficiently processing continuous k-nn queries on data streams. In Proc. of Int. Conf. on Data Engineering (ICDE), pages 156--165, 2007."},{"key":"e_1_2_1_2_1","first-page":"421430","volume-title":"Proc. of Int. Conf. on Data Engineering (ICDE)","author":"B\u00f6rzs\u00f6nyi S.","year":"2001","unstructured":"S. B\u00f6rzs\u00f6nyi , D. Kossmann , and K. Stocker . The skyline operator . In Proc. of Int. Conf. on Data Engineering (ICDE) , page 421430 , 2001 . S. B\u00f6rzs\u00f6nyi, D. Kossmann, and K. Stocker. The skyline operator. In Proc. of Int. Conf. on Data Engineering (ICDE), page 421430, 2001."},{"key":"e_1_2_1_3_1","first-page":"64","volume-title":"Proc. of Int. Conf. on Data Engineering (ICDE)","author":"Chaudhuri S.","year":"2006","unstructured":"S. Chaudhuri , N. N. Dalvi , and R. Kaushik . Robust cardinality and cost estimation for skyline operator . In Proc. of Int. Conf. on Data Engineering (ICDE) , page 64 , 2006 . 10.1109\/ICDE.2006.131 S. Chaudhuri, N. N. Dalvi, and R. Kaushik. Robust cardinality and cost estimation for skyline operator. In Proc. of Int. Conf. on Data Engineering (ICDE), page 64, 2006. 10.1109\/ICDE.2006.131"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/11535331_10","volume-title":"Proc. of the Int. Symposium on Spatial and Temporal Databases (SSTD)","author":"Du Y.","year":"2005","unstructured":"Y. Du , D. Zhang , and T. Xia . The Optimal-Location query . In Proc. of the Int. Symposium on Spatial and Temporal Databases (SSTD) , pages 163 -- 180 , 2005 . 10.1007\/11535331_10 Y. Du, D. Zhang, and T. Xia. The Optimal-Location query. In Proc. of the Int. Symposium on Spatial and Temporal Databases (SSTD), pages 163--180, 2005. 10.1007\/11535331_10"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_6_1","first-page":"47","volume-title":"Proc. of the Int. Conf. on Management of Data (SIGMOD)","author":"Guttman A.","year":"1984","unstructured":"A. Guttman . R-trees : a dynamic index structure for spatial searching . In Proc. of the Int. Conf. on Management of Data (SIGMOD) , pages 47 -- 57 , Boston, Massachusetts , 1984 . 10.1145\/602259.602266 A. Guttman. R-trees: a dynamic index structure for spatial searching. In Proc. of the Int. Conf. on Management of Data (SIGMOD), pages 47--57, Boston, Massachusetts, 1984. 10.1145\/602259.602266"},{"key":"e_1_2_1_7_1","first-page":"1","volume-title":"Geographic Data Mining and Knowledge Discovery","author":"Han J.","year":"2001","unstructured":"J. Han , M. Kamber , and A. K. H. Tung . Spatial clustering methods in data mining: A survey . Geographic Data Mining and Knowledge Discovery , pages 1 -- 29 , 2001 . J. Han, M. Kamber, and A. K. H. Tung. Spatial clustering methods in data mining: A survey. Geographic Data Mining and Knowledge Discovery, pages 1--29, 2001."},{"key":"e_1_2_1_8_1","first-page":"201","volume-title":"Proc. of the Int. Conf. on Management of Data (SIGMOD)","author":"Korn F.","year":"2000","unstructured":"F. Korn and S. Muthukrishnan . Influence sets based on reverse nearest neighbor queries . In Proc. of the Int. Conf. on Management of Data (SIGMOD) , pages 201 -- 212 , 2000 . 10.1145\/342009.335415 F. Korn and S. Muthukrishnan. Influence sets based on reverse nearest neighbor queries. In Proc. of the Int. Conf. on Management of Data (SIGMOD), pages 201--212, 2000. 10.1145\/342009.335415"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272749"},{"key":"e_1_2_1_10_1","first-page":"635","volume-title":"Proc. of the Int. Conf. on Management of Data (SIGMOD)","author":"Mouratidis K.","year":"2006","unstructured":"K. Mouratidis , S. Bakiras , and D. Papadias . Continuous monitoring of top-k queries over sliding windows . In Proc. of the Int. Conf. on Management of Data (SIGMOD) , pages 635 -- 646 , 2006 . 10.1145\/1142473.1142544 K. Mouratidis, S. Bakiras, and D. Papadias. Continuous monitoring of top-k queries over sliding windows. In Proc. of the Int. Conf. on Management of Data (SIGMOD), pages 635--646, 2006. 10.1145\/1142473.1142544"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/3-540-47724-1_23","volume-title":"Proc. of the Int. Symposium on Advances in Spatial and Temporal Databases (SSTD)","author":"Papadias D.","year":"2001","unstructured":"D. Papadias , P. Kalnis , J. Zhang , and Y Tao . Efficient OLAP operations in spatial data warehouses . In Proc. of the Int. Symposium on Advances in Spatial and Temporal Databases (SSTD) , pages 443 -- 459 . Springer-Verlag , 2001 . D. Papadias, P. Kalnis, J. Zhang, and Y Tao. Efficient OLAP operations in spatial data warehouses. In Proc. of the Int. Symposium on Advances in Spatial and Temporal Databases (SSTD), pages 443--459. Springer-Verlag, 2001."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_2_1_13_1","first-page":"2012","volume-title":"Proc. of Int. Conf. on Pattern Recognition (ICPR)","author":"Pekalska E.","year":"2000","unstructured":"E. Pekalska and R. P. W. Duin . Classifiers for dissimilarity-based pattern recognition . In Proc. of Int. Conf. on Pattern Recognition (ICPR) , pages 2012 -- 2016 , 2000 . E. Pekalska and R. P. W. Duin. Classifiers for dissimilarity-based pattern recognition. In Proc. of Int. Conf. on Pattern Recognition (ICPR), pages 2012--2016, 2000."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/356924.356930"},{"key":"e_1_2_1_15_1","first-page":"946","volume-title":"Proc. of the Int. Conf. on Very Large Data Bases (VLDB)","author":"Xia T.","year":"2005","unstructured":"T. Xia , D. Zhang , E. Kanoulas , and Y. Du . On computing top-t most influential spatial sites . In Proc. of the Int. Conf. on Very Large Data Bases (VLDB) , pages 946 -- 957 , 2005 . T. Xia, D. Zhang, E. Kanoulas, and Y. Du. On computing top-t most influential spatial sites. In Proc. of the Int. Conf. on Very Large Data Bases (VLDB), pages 946--957, 2005."},{"key":"e_1_2_1_16_1","first-page":"1076","volume-title":"Proc. of Int. Conf. on Data Engineering (ICDE)","author":"Yiu M. L.","year":"2007","unstructured":"M. L. Yiu , X. Dai , N. Mamoulis , and M. Vaitis . Top-k spatial preference queries . In Proc. of Int. Conf. on Data Engineering (ICDE) , pages 1076 -- 1085 , 2007 . M. L. Yiu, X. Dai, N. Mamoulis, and M. Vaitis. Top-k spatial preference queries. In Proc. of Int. Conf. on Data Engineering (ICDE), pages 1076--1085, 2007."},{"key":"e_1_2_1_17_1","unstructured":"M. L. Yiu H. Lu N. Mamoulis and M. Vaitis. Ranking spatial data by quality preferences. Transactions on Knowledge and Data Engineering (TKDE) to appear. 10.1109\/TKDE.2010.119   M. L. Yiu H. Lu N. Mamoulis and M. Vaitis. Ranking spatial data by quality preferences. Transactions on Knowledge and Data Engineering (TKDE) to appear . 10.1109\/TKDE.2010.119"},{"key":"e_1_2_1_18_1","first-page":"509","volume-title":"Proc. of the Int. Conf. on Management of Data (SIGMOD)","author":"Zhang Z.","year":"2009","unstructured":"Z. Zhang , Y. Yang , R. Cai , D. Papadias , and A. K. H. Tung . Kernel-based skyline cardinality estimation . In Proc. of the Int. Conf. on Management of Data (SIGMOD) , pages 509 -- 522 , 2009 . 10.1145\/1559845.1559899 Z. Zhang, Y. Yang, R. Cai, D. Papadias, and A. K. H. Tung. Kernel-based skyline cardinality estimation. In Proc. of the Int. Conf. on Management of Data (SIGMOD), pages 509--522, 2009. 10.1145\/1559845.1559899"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1921071.1921076","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:51:41Z","timestamp":1672221101000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1921071.1921076"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["10.14778\/1921071.1921076"],"URL":"https:\/\/doi.org\/10.14778\/1921071.1921076","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,11]]}}}