{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T05:28:52Z","timestamp":1747805332474},"reference-count":39,"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>The goal of a<jats:italic>threshold query<\/jats:italic>is to detect all objects whose score exceeds a given threshold. This type of query is used in many settings, such as data mining, event triggering, and top-<jats:italic>k<\/jats:italic>selection. Often, threshold queries are performed over<jats:italic>distributed data<\/jats:italic>. Given database relations that are distributed over many nodes, an object's score is computed by aggregating the value of each attribute, applying a given scoring function over the aggregation, and thresholding the function's value. However, joining all the distributed relations to a central database might incur prohibitive overheads in bandwidth, CPU, and storage accesses. Efficient algorithms required to reduce these costs exist only for monotonic aggregation threshold queries and certain specific scoring functions.<\/jats:p><jats:p>We present a novel approach for efficiently performing general distributed threshold queries. To the best of our knowledge, this is the first solution to the problem of performing such queries with general scoring functions. We first present a solution for monotonic functions, and then introduce a technique to solve for other functions by representing them as a difference of monotonic functions. Experiments with real-world data demonstrate the method's effectiveness in achieving low communication and access costs.<\/jats:p>","DOI":"10.14778\/1921071.1921072","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"46-57","source":"Crossref","is-referenced-by-count":12,"title":["Distributed threshold querying of general functions by a difference of monotonic representation"],"prefix":"10.14778","volume":"4","author":[{"given":"Guy","family":"Sagy","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Keren","sequence":"additional","affiliation":[{"name":"Haifa University, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Izchak","family":"Sharfman","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Assaf","family":"Schuster","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/gregsadetsky.com\/aol-data\/. http:\/\/gregsadetsky.com\/aol-data\/."},{"key":"e_1_2_1_2_1","unstructured":"http:\/\/www.netflix.com\/. http:\/\/www.netflix.com\/."},{"key":"e_1_2_1_3_1","first-page":"174","volume-title":"ICDE Conf.","author":"Balke W. T.","year":"2005"},{"key":"e_1_2_1_4_1","first-page":"421","volume-title":"ICDE Conf.","author":"Borzsonyi S.","year":"2001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1145\/1011767.1011798","volume-title":"PODC Conf.","author":"Cao P.","year":"2004"},{"issue":"2","key":"e_1_2_1_6_1","first-page":"80","article-title":"A framework for learning from distributed data using sufficient statistics and its application to learning decision trees","volume":"1","author":"Caragea D.","year":"2004","journal-title":"Int. J. Hybrid Intell. Syst."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"N. L. Carothers. Real Analysis. Cambridge University Press 2000. N. L. Carothers. Real Analysis . Cambridge University Press 2000.","DOI":"10.1017\/CBO9780511814228"},{"key":"e_1_2_1_8_1","first-page":"346","volume-title":"SIGMOD Conf.","author":"Chang K. C.-C.","year":"2002"},{"key":"e_1_2_1_9_1","first-page":"48","volume-title":"PAKDD Conf.","author":"Cheung D. W.-L.","year":"1998"},{"issue":"1","key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"85","DOI":"10.14778\/1687627.1687638","article-title":"Randomized multi-pass streaming skyline algorithms","volume":"2","author":"Sarma A. Das","year":"2009","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1145\/375551.375567","volume-title":"PODS Conf.","author":"Fagin R.","year":"2001"},{"key":"e_1_2_1_12_1","first-page":"67","volume-title":"ICDM Conf.","author":"Giannella C.","year":"2004"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0029-7"},{"key":"e_1_2_1_14_1","volume-title":"Morgan Kaufmann Publishers Inc.","author":"Han J.","year":"2005"},{"key":"e_1_2_1_15_1","first-page":"134","volume-title":"INFOCOM conf.","author":"Huang L.","year":"2007"},{"key":"e_1_2_1_16_1","volume-title":"HotNets Workshop","author":"Jain A.","year":"2004"},{"key":"e_1_2_1_17_1","first-page":"289","volume-title":"SIGMOD","author":"Keralapura R.","year":"2006"},{"key":"e_1_2_1_18_1","first-page":"275","volume-title":"VLDB Conf.","author":"Kossmann D.","year":"2002"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1145\/1015467.1015492","volume-title":"SIGCOMM Conf.","author":"Lakhina A.","year":"2004"},{"issue":"4","key":"e_1_2_1_20_1","first-page":"361","article-title":"Rcv1: A new benchmark collection for text categorization research","volume":"5","author":"Lewis D. D.","year":"2004","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_21_1","first-page":"369","volume-title":"ICDE Conf.","author":"Marian A.","year":"2002"},{"key":"e_1_2_1_22_1","first-page":"637","volume-title":"VLDB Conf.","author":"Michel S.","year":"2005"},{"key":"e_1_2_1_23_1","first-page":"60","volume-title":"Middleware","author":"Michel S.","year":"2005"},{"key":"e_1_2_1_24_1","first-page":"563","volume-title":"SIGMOD Conf.","author":"Olston C.","year":"2003"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_2_1_26_1","volume-title":"Lawrence Erlbaum Associates","author":"Park B.-H.","year":"2002"},{"key":"e_1_2_1_27_1","first-page":"1","volume-title":"SIGMOD Conf.","author":"Ramaswamy S.","year":"2008"},{"key":"e_1_2_1_28_1","first-page":"29","volume-title":"LREC conf.","author":"Rose T.","year":"2002"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1145\/375663.375728","volume-title":"SIGMOD Conf.","author":"Schuster A.","year":"2001"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292609.1292613"},{"key":"e_1_2_1_31_1","first-page":"301","volume-title":"PODS Conf.","author":"Sharfman I.","year":"2008"},{"key":"e_1_2_1_32_1","volume-title":"WebDB Workshop","author":"Suel T.","year":"2002"},{"key":"e_1_2_1_33_1","first-page":"301","volume-title":"VLDB Conf.","author":"Tan K.-L.","year":"2001"},{"key":"e_1_2_1_34_1","first-page":"103","volume-title":"SIGMOD Conf.","author":"Xin D.","year":"2007"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1145\/1014052.1014090","volume-title":"KDD","author":"Xiong H.","year":"2004"},{"key":"e_1_2_1_36_1","first-page":"65","volume-title":"DEXA Conf.","author":"Yu H.","year":"2005"},{"key":"e_1_2_1_37_1","first-page":"152","volume-title":"CIKM Conf.","author":"Zhang J.","year":"2006"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1145\/1142473.1142515","volume-title":"SIGMOD Conf.","author":"Zhang Z.","year":"2006"},{"key":"e_1_2_1_39_1","first-page":"298","volume-title":"PODS Conf.","author":"Zhao Q.","year":"2006"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1921071.1921072","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T23:55:22Z","timestamp":1690415722000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1921071.1921072"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["10.14778\/1921071.1921072"],"URL":"https:\/\/doi.org\/10.14778\/1921071.1921072","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,11]]}}}