{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T11:01:02Z","timestamp":1777806062824,"version":"3.51.4"},"reference-count":41,"publisher":"SAGE Publications","issue":"5","license":[{"start":{"date-parts":[[2018,4,6]],"date-time":"2018-04-06T00:00:00Z","timestamp":1522972800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer Security"],"published-print":{"date-parts":[[2018,8,9]]},"abstract":"<jats:p>Given a set of multi-dimensional points, a k-skyband query retrieves those points dominated by no more than k other points. k-skyband queries are an important type of multi-criteria analysis with diverse applications in practice. In this paper, we investigate techniques to answer k-skyband queries with differential privacy. We first propose a general technique BBS-Priv , which accepts any differentially private spatial decomposition tree as input and leverages data synthesis to answer k-skyband queries privately. We then show that, though quite a few private spatial decomposition trees are proposed in the literature, they are mainly designed to answer spatial range queries. Directly integrating them with BBS-Priv would introduce too much noise to generate useful k-skyband results. To address this problem, we propose a novel spatial decomposition technique k-skyband tree specially optimized for k-skyband queries, which partitions data adaptively based on the parameter k and performs finer partitions on the regions that are likely to contain k-skyband results. We further propose techniques to generate a k-skyband tree over spatial data that satisfies differential privacy, and combine BBS-Priv with the private k-skyband tree to answer k-skyband queries. We conduct extensive experiments based on two real-world datasets and three synthetic datasets that are commonly used for evaluating k-skyband queries. The results show that the proposed scheme significantly outperforms existing differentially private spatial decomposition schemes and achieves high utility when privacy budgets are properly allocated.<\/jats:p>","DOI":"10.3233\/jcs-171101","type":"journal-article","created":{"date-parts":[[2018,4,6]],"date-time":"2018-04-06T11:21:06Z","timestamp":1523013666000},"page":"647-676","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["<i>k<\/i>\n                    -Skyband query answering with differential\u00a0privacy"],"prefix":"10.1177","volume":"26","author":[{"given":"Ling","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Computer Science, North Carolina State University, NC, USA. E-mails:\u00a0,\u00a0"}]},{"given":"Ting","family":"Yu","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute, Hamad Bin Khalifa University, Doha, Qatar. E-mail:\u00a0"}]},{"given":"Rada","family":"Chirkova","sequence":"additional","affiliation":[{"name":"Department of Computer Science, North Carolina State University, NC, USA. E-mails:\u00a0,\u00a0"}]}],"member":"179","published-online":{"date-parts":[[2018,4,6]]},"reference":[{"key":"ref001","unstructured":"http:\/\/kdd.ics.uci.edu\/databases\/covertype\/covertype.html."},{"key":"ref002","doi-asserted-by":"crossref","unstructured":"B.\u00a0Barak, K.\u00a0Chaudhuri, C.\u00a0Dwork, S.\u00a0Kale, F.\u00a0McSherry and K.\u00a0Talwar, Privacy, accuracy, and consistency too: A holistic solution to contingency table release, in: PODS, 2007.","DOI":"10.1145\/1265530.1265569"},{"key":"ref003","doi-asserted-by":"crossref","unstructured":"M.\u00a0Blanton and E.\u00a0Aguiar, Private and oblivious set and multiset operations, in: ASIACCS, 2012.","DOI":"10.1145\/2414456.2414479"},{"key":"ref004","unstructured":"S.\u00a0Borzsony, D.\u00a0Kossmann and K.\u00a0Stocker, The skyline operator, in: ICDE, 2001."},{"key":"ref005","doi-asserted-by":"crossref","unstructured":"C.\u00a0Cachin, Efficient private bidding and auctions with an oblivious third party, in: CCS, 1999.","DOI":"10.1145\/319709.319726"},{"key":"ref006","doi-asserted-by":"crossref","unstructured":"L.\u00a0Chen, S.\u00a0Gao and K.\u00a0Anyanwu, Efficiently evaluating skyline queries on RDF databases, in: ESWC, 2011.","DOI":"10.1007\/978-3-642-21064-8_9"},{"key":"ref007","doi-asserted-by":"crossref","unstructured":"L.\u00a0Chen, T.\u00a0Yu and R.\u00a0Chirkova, WaveCluster with differential privacy, in: CIKM, 2015.","DOI":"10.1145\/2806416.2806546"},{"key":"ref008","doi-asserted-by":"crossref","unstructured":"L.\u00a0Chen, T.\u00a0Yu and R.\u00a0Chirkova, Differentially private K-skyband query answering through adaptive spatial decomposition, in: DBSec, 2017, pp.\u00a0142\u2013163.","DOI":"10.1007\/978-3-319-61176-1_8"},{"key":"ref009","doi-asserted-by":"crossref","unstructured":"G.\u00a0Cormode, C.\u00a0Procopiuc, D.\u00a0Srivastava, E.\u00a0Shen and T.\u00a0Yu, Differentially private spatial decompositions, in: ICDE, 2012.","DOI":"10.1109\/ICDE.2012.16"},{"key":"ref010","doi-asserted-by":"crossref","unstructured":"M.\u00a0de Berg, O.\u00a0Cheong, M.\u00a0van Kreveld and M.\u00a0Overmars, Computational Geometry: Algorithms and Applications, 2008. doi:10.1007\/978-3-540-77974-2.","DOI":"10.1007\/978-3-540-77974-2"},{"key":"ref011","unstructured":"C.\u00a0Dwork, Differential privacy: A survey of results, in: TAMC, 2008."},{"key":"ref012","doi-asserted-by":"crossref","unstructured":"C.\u00a0Dwork and J.\u00a0Lei, Differential privacy and robust statistics, in: STOC, 2009.","DOI":"10.1145\/1536414.1536466"},{"key":"ref013","doi-asserted-by":"crossref","unstructured":"C.\u00a0Dwork, F.\u00a0McSherry, K.\u00a0Nissim and A.\u00a0Smith, Calibrating noise to sensitivity in private data analysis, in: TCC, 2006.","DOI":"10.1007\/11681878_14"},{"key":"ref014","doi-asserted-by":"crossref","unstructured":"C.\u00a0Dwork and A.\u00a0Roth, The algorithmic foundations of differential privacy, Found. Trends Theor. Comput. Sci. 9 (2014).","DOI":"10.1561\/9781601988195"},{"key":"ref015","doi-asserted-by":"crossref","unstructured":"D.\u00a0Feldman, A.\u00a0Fiat, H.\u00a0Kaplan and K.\u00a0Nissim, Private coresets, in: STOC, 2009.","DOI":"10.1145\/1536414.1536465"},{"key":"ref016","doi-asserted-by":"crossref","unstructured":"X.\u00a0Feng, Y.\u00a0Gao, T.\u00a0Jiang, L.\u00a0Chen, X.\u00a0Miao and Q.\u00a0Liu, Parallel\n                      k\n                      -skyband computation on multicore architecture, in: APWeb, 2013.","DOI":"10.1007\/978-3-642-37401-2_79"},{"key":"ref017","doi-asserted-by":"crossref","unstructured":"M.J.\u00a0Freedman, K.\u00a0Nissim and B.\u00a0Pinkas, Efficient private matching and set intersection, in: EUROCRYPT, 2004.","DOI":"10.1007\/978-3-540-24676-3_1"},{"key":"ref018","doi-asserted-by":"crossref","unstructured":"G.\u00a0Ghinita, K.\u00a0Zhao, D.\u00a0Papadias and P.\u00a0Kalnis, A reciprocal framework for spatial K-anonymity, Inf. Syst. 35(3) (2010).","DOI":"10.1016\/j.is.2009.10.001"},{"key":"ref019","doi-asserted-by":"crossref","unstructured":"D.S.\u00a0Gordon, H.\u00a0Carmit, J.\u00a0Katz and Y.\u00a0Lindell, Complete fairness in secure two-party computation, in: STOC, 2008.","DOI":"10.1145\/1374376.1374436"},{"key":"ref020","doi-asserted-by":"crossref","unstructured":"D.\u00a0Harnik, M.\u00a0Naor, O.\u00a0Reingold and A.\u00a0Rosen, Completeness in two-party secure computation: A computational view, in: STOC, 2004.","DOI":"10.1145\/1007352.1007395"},{"key":"ref021","doi-asserted-by":"crossref","unstructured":"M.\u00a0Hay, V.\u00a0Rastogi, G.\u00a0Miklau and D.\u00a0Suciu, Boosting the accuracy of differentially private histograms through consistency, PVLDB 3 (2010).","DOI":"10.14778\/1920841.1920970"},{"key":"ref022","doi-asserted-by":"crossref","unstructured":"A.\u00a0Inan, M.\u00a0Kantarcioglu, G.\u00a0Ghinita and E.\u00a0Bertino, Private record matching using differential privacy, in: EDBT, 2010.","DOI":"10.1145\/1739041.1739059"},{"key":"ref023","doi-asserted-by":"crossref","unstructured":"S.P.\u00a0Kasiviswanathan, H.K.\u00a0Lee, K.\u00a0Nissim, S.\u00a0Raskhodnikova and A.\u00a0Smith, What can we learn privately? in: FOCS, 2008.","DOI":"10.1109\/FOCS.2008.27"},{"key":"ref024","doi-asserted-by":"crossref","unstructured":"K.\u00a0Kodama, Y.\u00a0Iijima, X.\u00a0Guo and Y.\u00a0Ishikawa, Skyline queries based on user locations and preferences for making location-based recommendations, in: Int\u2019l Workshop on Location Based Social Networks, 2009.","DOI":"10.1145\/1629890.1629893"},{"key":"ref025","doi-asserted-by":"crossref","unstructured":"J.J.\u00a0Levandoski, M.F.\u00a0Mokbel and M.E.\u00a0Khalefa, Preference query evaluation over expensive attributes, in: CIKM, 2010.","DOI":"10.1145\/1871437.1871481"},{"key":"ref026","doi-asserted-by":"crossref","unstructured":"A.\u00a0Machanavajjhala, D.\u00a0Kifer, J.\u00a0Gehrke and M.\u00a0Venkitasubramaniam, L-diversity: Privacy beyond K-anonymity, ACM Trans. Knowl. Discov. Data 1(1) (2007).","DOI":"10.1145\/1217299.1217302"},{"key":"ref027","doi-asserted-by":"crossref","unstructured":"M.\u00a0Magnani, I.\u00a0Assent and M.L.\u00a0Mortensen, Taking the big picture: Representative skylines based on significance and diversity, VLDB J. 23(5) (2014).","DOI":"10.1007\/s00778-014-0352-3"},{"key":"ref028","doi-asserted-by":"crossref","unstructured":"F.\u00a0McSherry, Privacy integrated queries: An extensible platform for privacy-preserving data analysis, Commun. ACM 53(9) (2010).","DOI":"10.1145\/1810891.1810916"},{"key":"ref029","doi-asserted-by":"crossref","unstructured":"F.\u00a0McSherry and K.\u00a0Talwar, Mechanism design via differential privacy, in: FOCS, 2007.","DOI":"10.1109\/FOCS.2007.4389483"},{"key":"ref030","unstructured":"NBA players statistics, http:\/\/www.hoopsstats.com\/basketball\/fantasy\/nba\/playerstats."},{"key":"ref031","doi-asserted-by":"crossref","unstructured":"K.\u00a0Nissim, S.\u00a0Raskhodnikova and A.\u00a0Smith, Smooth sensitivity and sampling in private data analysis, in: STOC, 2007.","DOI":"10.1145\/1250790.1250803"},{"key":"ref032","doi-asserted-by":"crossref","unstructured":"D.\u00a0Papadias, Y.\u00a0Tao, G.\u00a0Fu and B.\u00a0Seeger, Progressive skyline computation in database systems, ACM Trans. Database Syst. 30(1) (2005).","DOI":"10.1145\/1061318.1061320"},{"key":"ref033","unstructured":"P.\u00a0Samarati and L.\u00a0Sweeney, Protecting privacy when disclosing information: K-anonymity and its enforcement through generalization and suppression, in: IEEE Security & Privacy, 1998."},{"key":"ref034","unstructured":"G.\u00a0Sheikholeslami, S.\u00a0Chatterjee and A.\u00a0Zhang, WaveCluster: A multi-resolution clustering approach for very large spatial databases, in: VLDB, 1998."},{"key":"ref035","doi-asserted-by":"crossref","unstructured":"G.\u00a0Sheikholeslami, S.\u00a0Chatterjee and A.\u00a0Zhang, WaveCluster: A wavelet-based clustering approach for spatial data in very large databases, The VLDB Journal 8(3\u20134) (2000).","DOI":"10.1007\/s007780050009"},{"key":"ref036","unstructured":"G.\u00a0Turkiyyah, Hanan Samet, What is in there, where is it, and what is it close to: Dealing with spatial and metric data, Foundations of multidimensional and metric data structures, Morgan Kaufmann (2006), Computer-Aided Design 40(4) (2008)."},{"key":"ref037","unstructured":"J.\u00a0Vaidya and C.\u00a0Clifton, Privacy-preserving top-k queries, in: ICDE, 2005."},{"key":"ref038","doi-asserted-by":"crossref","unstructured":"G.\u00a0Valkanas, A.N.\u00a0Papadopoulos and D.\u00a0Gunopulos, SkyDiver: A framework for skyline diversification, in: EDBT, 2013.","DOI":"10.1145\/2452376.2452424"},{"key":"ref039","doi-asserted-by":"crossref","unstructured":"J.\u00a0Xu, Z.\u00a0Zhang, X.\u00a0Xiao, Y.\u00a0Yang, G.\u00a0Yu and M.\u00a0Winslett, Differentially private histogram publication, VLDB J. 22(6) (2013).","DOI":"10.1007\/s00778-013-0309-y"},{"key":"ref040","doi-asserted-by":"crossref","unstructured":"J.\u00a0Zhang, X.\u00a0Xiao and X.\u00a0Xie, PrivTree: A differentially private algorithm for hierarchical decompositions, in: SIGMOD, 2016.","DOI":"10.1145\/2882903.2882928"},{"key":"ref041","doi-asserted-by":"crossref","unstructured":"J.\u00a0Zhang, X.\u00a0Xiao, Y.\u00a0Yang, Z.\u00a0Zhang and M.\u00a0Winslett, PrivGene: Differentially private model fitting using genetic algorithms, in: SIGMOD, 2013.","DOI":"10.1145\/2463676.2465330"}],"container-title":["Journal of Computer Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-171101","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JCS-171101","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-171101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T20:45:14Z","timestamp":1777495514000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JCS-171101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,6]]},"references-count":41,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,8,9]]}},"alternative-id":["10.3233\/JCS-171101"],"URL":"https:\/\/doi.org\/10.3233\/jcs-171101","relation":{},"ISSN":["0926-227X","1875-8924"],"issn-type":[{"value":"0926-227X","type":"print"},{"value":"1875-8924","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,6]]}}}