{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T08:54:25Z","timestamp":1773392065788,"version":"3.50.1"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,5]]},"abstract":"<jats:p>\n            Many modern applications deal with exponentially increasing data volumes and aid business-critical decisions in near real-time. Particularly in exploratory data analysis, the focus is on interactive querying and some degree of error in estimated results is tolerable. A common response to this challenge is approximate query processing, where the user is presented with a quick confidence interval estimate based on a sample of the data. In this work, we highlight some of the problems that are associated with this\n            <jats:italic>probabilistic<\/jats:italic>\n            approach when extended to more complex queries, both in semantic interpretation and the lack of a formal algebra. As an alternative, we propose\n            <jats:italic>deterministic<\/jats:italic>\n            approximate querying (DAQ) schemes, formalize a closed deterministic approximation algebra, and outline some design principles for DAQ schemes. We also illustrate the utility of this approach with an example deterministic online approximation scheme which uses a bitsliced index representation and computes the most significant bits of the result first. Our prototype scheme delivers speedups over exact aggregation and predicate evaluation, and outperforms sampling-based schemes for extreme value aggregations.\n          <\/jats:p>","DOI":"10.14778\/2777598.2777599","type":"journal-article","created":{"date-parts":[[2015,5,15]],"date-time":"2015-05-15T16:09:36Z","timestamp":1431706176000},"page":"898-909","source":"Crossref","is-referenced-by-count":38,"title":["DAQ"],"prefix":"10.14778","volume":"8","author":[{"given":"Navneet","family":"Potti","sequence":"first","affiliation":[{"name":"University of Wisconsin -- Madison"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jignesh M.","family":"Patel","sequence":"additional","affiliation":[{"name":"University of Wisconsin -- Madison"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"VLDB","author":"Acharya S.","year":"1999"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593667"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_1_5_1","volume-title":"IBM","author":"Haas P. J.","year":"1996"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/253262.253291"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261131"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375718"},{"key":"e_1_2_1_9_1","volume-title":"VLDB","author":"Olken F.","year":"1986"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/253262.253268"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816677"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066224"},{"key":"e_1_2_1_13_1","volume-title":"DAQ: A New Paradigm for Approximate Query Processing (Extended Version) at http:\/\/pages.cs.wisc.edu\/~nav\/DAQ-extended.pdf. Technical report","author":"Potti N.","year":"2014"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375669"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2031527"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132864"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588579"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2777598.2777599","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:17:14Z","timestamp":1672222634000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2777598.2777599"}},"subtitle":["a new paradigm for approximate query processing"],"short-title":[],"issued":{"date-parts":[[2015,5]]},"references-count":17,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2015,5]]}},"alternative-id":["10.14778\/2777598.2777599"],"URL":"https:\/\/doi.org\/10.14778\/2777598.2777599","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,5]]}}}