{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T11:08:29Z","timestamp":1772881709498,"version":"3.50.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,5,1]],"date-time":"2011-05-01T00:00:00Z","timestamp":1304208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004377","name":"Hong Kong Polytechnic University","doi-asserted-by":"publisher","award":["5333\/10E"],"award-info":[{"award-number":["5333\/10E"]}],"id":[{"id":"10.13039\/501100004377","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Danish Natural Science Research Council","award":["272-06-044209-072331"],"award-info":[{"award-number":["272-06-044209-072331"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2011,5]]},"abstract":"<jats:p>\n            Users of mobile services wish to retrieve nearby points of interest without disclosing their locations to the services. This article addresses the challenge of optimizing the query performance while satisfying given location privacy and query accuracy requirements. The article's proposal, SpaceTwist, aims to offer location privacy for\n            <jats:italic>k<\/jats:italic>\n            nearest neighbor (\n            <jats:italic>k<\/jats:italic>\n            NN) queries at low communication cost without requiring a trusted anonymizer. The solution can be used with a conventional DBMS as well as with a server optimized for location-based services. In particular, we believe that this is the first solution that expresses the server-side functionality in a single SQL statement. In its basic form, SpaceTwist utilizes well-known incremental NN query processing on the server. When augmented with a server-side granular search technique, SpaceTwist is capable of exploiting relaxed query accuracy guarantees for obtaining better performance. We extend SpaceTwist with so-called ring ranking, which improves the communication cost, delayed termination, which improves the privacy afforded the user, and the ability to function in spatial networks in addition to Euclidean space. We report on analytical and empirical studies that offer insight into the properties of SpaceTwist and suggest that our proposal is indeed capable of offering privacy with very good performance in realistic settings.\n          <\/jats:p>","DOI":"10.1145\/1966385.1966388","type":"journal-article","created":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T11:51:38Z","timestamp":1307361098000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Design and analysis of a ranking approach to private location-based services"],"prefix":"10.1145","volume":"36","author":[{"given":"Man Lung","family":"Yiu","sequence":"first","affiliation":[{"name":"Hong Kong Polytechnic University"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aarhus University"}]},{"given":"Jesper","family":"M\u00f8ller","sequence":"additional","affiliation":[{"name":"Aalborg University"}]},{"given":"Hua","family":"Lu","sequence":"additional","affiliation":[{"name":"Aalborg University"}]}],"member":"320","published-online":{"date-parts":[[2011,6,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304184"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the Conference on Data and Applications Security and Privacy (DBSec). 47--60","author":"Ardagna C. A.","unstructured":"Ardagna , C. A. , Cremonini , M. , Damiani , E. , di Vimercati , S. D. C. , and Samarati , P . 2007. Location privacy protection through obfuscation-based techniques . In Proceedings of the Conference on Data and Applications Security and Privacy (DBSec). 47--60 . Ardagna, C. A., Cremonini, M., Damiani, E., di Vimercati, S. D. C., and Samarati, P. 2007. Location privacy protection through obfuscation-based techniques. In Proceedings of the Conference on Data and Applications Security and Privacy (DBSec). 47--60."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367531"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183614.1183674"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2007.19"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015231126594"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11957454_23"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the Conference on Advances in Spatial and Temporal Databases (SSTD). 258--275","author":"Chow C.-Y.","unstructured":"Chow , C.-Y. and Mokbel , M. F . 2007. Enabling private continuous queries for revealed user locations . In Proceedings of the Conference on Advances in Spatial and Temporal Databases (SSTD). 258--275 . Chow, C.-Y. and Mokbel, M. F. 2007. Enabling private continuous queries for revealed user locations. In Proceedings of the Conference on Advances in Spatial and Temporal Databases (SSTD). 258--275."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183471.1183500"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 426--435","author":"Ciaccia P.","unstructured":"Ciaccia , P. , Patella , M. , and Zezula , P . 1997. M-tree: An efficient access method for similarity search in metric spaces . In Proceedings of the International Conference on Very Large Databases (VLDB). 426--435 . Ciaccia, P., Patella, M., and Zezula, P. 1997. M-tree: An efficient access method for similarity search in metric spaces. In Proceedings of the International Conference on Very Large Databases (VLDB). 426--435."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11428572_10"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11556114_3"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2005.48"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376631"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings on the Conference on Advances in Spatial and Temporal Databases (SSTD). 758--769","author":"Ghinita G.","unstructured":"Ghinita , G. , Kalnis , P. , and Skiadopoulos , S . 2007a. MobiHide: A mobile peer-to-peer system for anonymous location-based queries . In Proceedings on the Conference on Advances in Spatial and Temporal Databases (SSTD). 758--769 . Ghinita, G., Kalnis, P., and Skiadopoulos, S. 2007a. MobiHide: A mobile peer-to-peer system for anonymous location-based queries. In Proceedings on the Conference on Advances in Spatial and Temporal Databases (SSTD). 758--769."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242623"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 491--500","author":"Gravano L.","unstructured":"Gravano , L. , Ipeirotis , P. G. , Jagadish , H. V. , Koudas , N. , Muthukrishnan , S. , and Srivastava , D . 2001. Approximate string joins in a database (almost) for free . In Proceedings of the International Conference on Very Large Databases (VLDB). 491--500 . Gravano, L., Ipeirotis, P. G., Jagadish, H. V., Koudas, N., Muthukrishnan, S., and Srivastava, D. 2001. Approximate string joins in a database (almost) for free. In Proceedings of the International Conference on Very Large Databases (VLDB). 491--500."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066116.1189037"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSECP.2004.1281242"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/320248.320255"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.15"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189769.1189772"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007593"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_13"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071612"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03511-1_2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190662"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings on the Conference on Advances in Spatial and Temporal Databases (SSTD). 239--257","author":"Khoshgozaran A.","unstructured":"Khoshgozaran , A. and Shahabi , C . 2007. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy . In Proceedings on the Conference on Advances in Spatial and Temporal Databases (SSTD). 239--257 . Khoshgozaran, A. and Shahabi, C. 2007. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy. In Proceedings on the Conference on Advances in Spatial and Temporal Databases (SSTD). 239--257."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the IEEE International Conference on Pervasive Services (ICPS). 1248","author":"Kido H.","unstructured":"Kido , H. , Yanagisawa , Y. , and Satoh , T . 2005. An anonymous communication technique using dummies for location-based services . In Proceedings of the IEEE International Conference on Pervasive Services (ICPS). 1248 . Kido, H., Yanagisawa, Y., and Satoh, T. 2005. An anonymous communication technique using dummies for location-based services. In Proceedings of the IEEE International Conference on Pervasive Services (ICPS). 1248."},{"key":"e_1_2_1_32_1","volume-title":"Poisson Processes","author":"Kingman J. F. C.","unstructured":"Kingman , J. F. C. 1993. Poisson Processes . Oxford University Press . Kingman, J. F. C. 1993. Poisson Processes. Oxford University Press."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2007.4400994"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142488"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SUTC.2008.56"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1626536.1626540"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 763--774","author":"Mokbel M. F.","unstructured":"Mokbel , M. F. , Chow , C.-Y. , and Aref , W. G . 2006. The new casper: Query processing for location services without compromising privacy . In Proceedings of the International Conference on Very Large Databases (VLDB). 763--774 . Mokbel, M. F., Chow, C.-Y., and Aref, W. G. 2006. The new casper: Query processing for location services without compromising privacy. In Proceedings of the International Conference on Very Large Databases (VLDB). 763--774."},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"M\u00f8ller J. and Waagepetersen R. P. 2004. Statistical Inference and Simulation for Spatial Point Processes. Chapman and Hall\/CRC Boca Raton.  M\u00f8ller J. and Waagepetersen R. P. 2004. Statistical Inference and Simulation for Spatial Point Processes. Chapman and Hall\/CRC Boca Raton.","DOI":"10.1201\/9780203496930"},{"key":"e_1_2_1_39_1","unstructured":"M\u00f8ller J. and Yiu M. L. 2010. Probabilistic results for a mobile service scenario. Research rep. R-2010-03 Department of Mathematical Sciences Aalborg University. To appear in Advances in Applied Probability.  M\u00f8ller J. and Yiu M. L. 2010. Probabilistic results for a mobile service scenario. Research rep. R-2010-03 Department of Mathematical Sciences Aalborg University. To appear in Advances in Applied Probability."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.48"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470317013"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066204"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 802--813","author":"Papadias D.","unstructured":"Papadias , D. , Zhang , J. , Mamoulis , N. , and Tao , Y . 2003. Query processing in spatial network databases . In Proceedings of the International Conference on Very Large Databases (VLDB). 802--813 . Papadias, D., Zhang, J., Mamoulis, N., and Tao, Y. 2003. Query processing in spatial network databases. In Proceedings of the International Conference on Very Large Databases (VLDB). 802--813."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02982-0_7"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.2307\/3213616"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223794"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218488502001648"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.48"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687745"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247494"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 463--475","author":"Xin D.","unstructured":"Xin , D. , Han , J. , Cheng , H. , and Li , X . 2006. Answering Top-k queries with multi-dimensional selections: The ranking cube approach . In Proceedings of the International Conference on Very Large Databases (VLDB). 463--475 . Xin, D., Han, J., Cheng, H., and Li, X. 2006. Answering Top-k queries with multi-dimensional selections: The ranking cube approach. In Proceedings of the International Conference on Very Large Databases (VLDB). 463--475."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2009.65"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0113-2"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the Conference on Data Engineering (ICDE). 4--15","author":"Yao B.","unstructured":"Yao , B. , Li , F. , and Kumar , P . 2010. K nearest neighbor queries and kNN-Joins in large relational databases (almost) for free . In Proceedings of the Conference on Data Engineering (ICDE). 4--15 . Yao, B., Li, F., and Kumar, P. 2010. K nearest neighbor queries and kNN-Joins in large relational databases (almost) for free. In Proceedings of the Conference on Data Engineering (ICDE). 4--15."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497445"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497462"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1966385.1966388","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1966385.1966388","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:22:25Z","timestamp":1750245745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1966385.1966388"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["10.1145\/1966385.1966388"],"URL":"https:\/\/doi.org\/10.1145\/1966385.1966388","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5]]},"assertion":[{"value":"2009-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}