research-article

K-Regret Queries Using Multiplicative Utility Functions

Authors:

Jia Cheng YaoAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 43, Issue 2

Article No.: 10, Pages 1 - 41

https://doi.org/10.1145/3230634

Published: 21 August 2018 Publication History

Abstract

The k-regret query aims to return a size-k subset S of a database D such that, for any query user that selects a data object from this size-k subset S rather than from database D, her regret ratio is minimized. The regret ratio here is modeled by the relative difference in the optimality between the locally optimal object in S and the globally optimal object in D. The optimality of a data object in turn is modeled by a utility function of the query user. Unlike traditional top-k queries, the k-regret query does not minimize the regret ratio for a specific utility function. Instead, it considers a family of infinite utility functions F, and aims to find a size-k subset that minimizes the maximum regret ratio of any utility function in F.

Studies on k-regret queries have focused on the family of additive utility functions, which have limitations in modeling individuals’ preferences and decision-making processes, especially for a common observation called the diminishing marginal rate of substitution (DMRS). We introduce k-regret queries with multiplicative utility functions, which are more expressive in modeling the DMRS, to overcome those limitations. We propose a query algorithm with bounded regret ratios. To showcase the applicability of the algorithm, we apply it to a special family of multiplicative utility functions, the Cobb-Douglas family of utility functions, and a closely related family of utility functions, the Constant Elasticity of Substitution family of utility functions, both of which are frequently used utility functions in microeconomics. After a further study of the query properties, we propose a heuristic algorithm that produces even smaller regret ratios in practice. Extensive experiments on the proposed algorithms confirm that they consistently achieve small maximum regret ratios.

References

[1]

2018. Retrieved March 30, 2018 from http://booking.com.

[2]

2018. How many products does Amazon.com sell—January 2018. Retrieved March 30, 208 from https://www.scrapehero.com/many-products-amazon-sell-january-2018/.

[3]

A. Amir, A. Efrat, P. Indyk, and H. Samet. 2001. Efficient regular data structures and algorithms for dilation, location, and proximity problems. Algorithmica 30, 2 (2001), 164--187.

Digital Library

[4]

C. H. Ang, H. Samet, and C. A. Shaffer. 1990. A new region expansion for quadtrees. IEEE Transactions on Pattern Analysis and Machine Intelligence 12, 7 (1990), 682--686.

Digital Library

[5]

Walid G. Aref and Hanan Samet. 1997. Efficient window block retrieval in quadtree-based spatial databases. Geoinformatica 1, 1 (1997), 59--91.

Digital Library

[6]

A. Asudeh, A. Nazi, N. Zhang, and G. Das. 2017. Efficient computation of regret-ratio minimizing set: A compact maxima representative. In International Conference on Management of Data (SIGMOD). Chicago, USA, 821--834.

Digital Library

[7]

E. R. Berndt. 1976. Reconciling alternative estimates of the elasticity of substitution. The Review of Economics and Statistics 58, 1 (1976), 59--68.

[8]

S. Börzsönyi, D. Kossmann, and K. Stocker. 2001. The skyline operator. In IEEE International Conference on Data Engineering (ICDE). Heidelberg, Germany, 421--430.

Digital Library

[9]

D. Braziunas and C. Boutilier. 2007. Minimax regret based elicitation of generalized additive utilities. In The 23rd Conference on Uncertainty in Artificial Intelligence. Vancouver, Canada, 25--32.

Digital Library

[10]

W. Cao, J. Li, H. Wang, K. Wang, R. Wang, R. C.-W. Wong, and W. Zhan. 2017. K-regret minimizing set: Efficient algorithms and hardness. In International Conference on Data Theory (ICDT). Venice, Italy, 11:1--11:19.

[11]

D. Cass. 1965. Optimum growth in an aggregative model of capital accumulation. The Review of Economic Studies 32, 3 (1965), 233--240.

[12]

D. W. Caves and L. R. Christensen. 1980. Global properties of flexible functional forms. The American Economic Review 70, 3 (1980), 422--432.

[13]

C.-Y. Chan, H. V. Jagadish, K.-L. Tan, A. K. H. Tung, and Z. Zhang. 2006. On high dimensional skylines. In International Conference on Extending Database Technology (EDBT). Munich, Germany, 478--495.

Digital Library

[14]

L. Chen, G. Cong, X. Cao, and K.-L. Tan. 2015. Temporal spatial-keyword top-k publish/subscribe. In IEEE International Conference on Data Engineering (ICDE). Seoul, South Korea, 255--266.

[15]

S. Chester, A. Thomo, S Venkatesh, and S. Whitesides. 2014. Computing k-regret minimizing sets. In Proceedings of the VLDB Endowment (PVLDB) 7, 5 (2014), 389--400.

Digital Library

[16]

C. W. Cobb and P. H. Douglas. 1928. A theory of production. The American Economic Review 18, 1 (1928), 139--165.

[17]

P. A Diamond. 1965. National debt in a neoclassical growth model. The American Economic Review 55, 5 (1965), 1126--1150.

[18]

P. A. Diamond, L. J. Helms, and J. A. Mirrlees. 1980. Optimal taxation in a stochastic economy. Journal of Public Economics 14, 1 (1980), 1--29.

[19]

Claudio Esperança and Hanan Samet. 2002. Experience with SAND-Tcl: A scripting tool for spatial databases. Journal of Visual Languages and Computing 13, 2 (2002), 229--255.

Digital Library

[20]

J. Huang, Z. Wen, J. Qi, R. Zhang, J. Chen, and Z. He. 2011. Top-k most influential locations selection. In ACM Conference of Information and Knowledge Management (CIKM). Glasgow, United Kingdom, 2377--2380.

Digital Library

[21]

I. F. Ilyas, G. Beskales, and M. A. Soliman. 2008. A survey of top-k query processing techniques in relational database systems. ACM Computing Surveys 40, 4 (2008), 11:1--11:58.

Digital Library

[22]

M. N. Katehakis and A. F. Veinott. 1987. The multi-armed bandit problem: Decomposition and computation. Mathematics of Operations Research 12, 2 (1987), 262--268.

[23]

R. L. Keeney and H. Raiffa. 1993. Decisions with Multiple Objectives: Preferences and Value Trade-Offs. Cambridge University Press, Cambridge, United Kingdom.

[24]

T. Kessler Faulkner, W. Brackenbury, and A. Lall. 2015. k-regret queries with nonlinear utilities. In Proceedings of the VLDB Endowment (PVLDB) 8, 13 (2015), 2098--2109.

Digital Library

[25]

M. E. Khalefa, M. F. Mokbel, and J. J. Levandoski. 2008. Skyline query processing for incomplete data. In IEEE International Conference on Data Engineering (ICDE). Cancún, México, 556--565.

Digital Library

[26]

M. E. Khalefa, M. F. Mokbel, and J. J. Levandoski. 2010. Skyline query processing for uncertain data. In ACM Conference of Information and Knowledge Management (CIKM). Toronto, Canada, 1293--1296.

Digital Library

[27]

K. Ligett and G. Piliouras. 2011. Beating the best nash without regret. SIGecom Exchanges 10, 1 (2011), 23--26.

Digital Library

[28]

X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang. 2007. Selecting stars: The k most representative skyline operator. In IEEE International Conference on Data Engineering (ICDE). Istanbul, Turkey, 86--95.

[29]

E. Miller. 2008. An assessment of CES and Cobb-Douglas production functions. Congressional Budget Office (2008).

[30]

Robert B. Miller. 1968. Response time in man-computer conversational transactions. In Proceedings of AFIPS Fall Joint Computer Conference. 267--277.

Digital Library

[31]

D. Nanongkai, A. Lall, A. D. Sarma, and K. Makino. 2012. Interactive regret minimization. In International Conference on Management of Data (SIGMOD). Scottsdale, USA, 109--120.

Digital Library

[32]

D. Nanongkai, A. D. Sarma, A. Lall, R. J. Lipton, and J. Xu. 2010. Regret-minimizing representative databases. In Proceedings of the VLDB Endowment (PVLDB) 3, 1--2 (2010), 1114--1124.

Digital Library

[33]

S. Nutanong, E. H. Jacox, and H. Samet. 2011. An incremental hausdorff distance calculation algorithm. In Proceedings of the VLDB Endowment (PVLDB) 4, 8 (2011), 506--517.

Digital Library

[34]

D. Papadias, Y. Tao, G. Fu, and B. Seeger. 2003. An optimal and progressive algorithm for skyline queries. In International Conference on Management of Data (SIGMOD). San Diego, USA, 467--478.

Digital Library

[35]

J. Pei, B. Jiang, X. Lin, and Y. Yuan. 2007. Probabilistic skylines on uncertain data. In International Conference on Very Large Data Bases (VLDB). Vienna, Austria, 15--26.

Digital Library

[36]

P. Peng and R. C.-W. Wong. 2014. Geometry approach for k-regret query. In IEEE International Conference on Data Engineering (ICDE). Chicago, USA, 772--783.

[37]

P. Peng and R. C.-W. Wong. 2015. K-hit query: Top-k query with probabilistic utility function. In International Conference on Management of Data (SIGMOD). Melbourne, Australia, 577--592.

Digital Library

[38]

H. Samet. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan-Kaufmann, San Francisco.

Digital Library

[39]

Hanan Samet, Houman Alborzi, František Brabec, Claudio Esperança, Gísli R. Hjaltason, Frank Morgan, and Egemen Tanin. 2003. Use of the SAND spatial browser for digital government applications. Communications of the ACM 46, 1 (2003), 61--64.

Digital Library

[40]

H. Samet, C. A. Shaffer, R. C. Nelson, Y. G. Huang, and A. Rosenfeld. 1987. Recent developments in linear quadtree-based geographic information systems. Image Vision Computing 5, 3 (1987), 187--197.

Digital Library

[41]

B. Shneiderman. 1984. Response time and display rate in human performance with computers. Computing Surveys 16, 3 (1984), 265--285.

Digital Library

[42]

M. A. Soliman, I. F. Ilyas, and K. C.-C. Chang. 2008. Probabilistic top-k and ranking-aggregate queries. ACM Transactions on Database Systems 33, 3 (2008), 13:1--13:54.

Digital Library

[43]

K.-L. Tan, P.-K. Eng, and B. C. Ooi. 2001. Efficient progressive skyline computation. In International Conference on Very Large Data Bases (VLDB). Roma, Italy, 301--310.

Digital Library

[44]

Y. Tao, L. Ding, X. Lin, and J. Pei. 2009. Distance-based representative skyline. In IEEE International Conference on Data Engineering (ICDE). Shanghai, China, 892--903.

Digital Library

[45]

H. Uzawa. 1962. Production functions with constant elasticities of substitution. The Review of Economic Studies 29, 4 (1962), 291--299.

[46]

H. R. Varian. 1992. Microeconomic Analysis. Norton 8 Company, New York.

[47]

A. D. Vîlcu and G. E. Vîlcu. 2011. On some geometric properties of the generalized CES production functions. Applied Mathematics and Computation 218, 1 (2011), 124--129.

[48]

G. E. Vîlcu. 2011. A geometric perspective on the generalized cobb-douglas production functions. Applied Mathematics Letters 24, 5 (2011), 777--783.

[49]

D. Wu, M. L. Yiu, G. Cong, and C. S. Jensen. 2012. Joint top-k spatial keyword query processing. IEEE Transactions on Knowledge and Data Engineering 24, 10 (2012), 1889--1903.

Digital Library

[50]

T. Xia, D. Zhang, and Y. Tao. 2008. On skylining with flexible dominance relation. In IEEE International Conference on Data Engineering (ICDE). Cancún, México, 1397--1399.

Digital Library

[51]

A. Zabalza. 1983. The Ces utility function, non-linear budget constraints and labour supply. Results on female participation and hours. The Economic Journal 93, 370 (1983), 312--330.

[52]

S. Zeighami and R. C.-W. Wong. 2016. Minimizing average regret ratio in database. In International Conference on Management of Data (SIGMOD). San Francisco, USA, 2265--2266.

Digital Library

Cited By

Zheng JMeng FWang YWang XWang SMa YHao Z(2024)Hybrid Regret Minimization: A Submodular ApproachIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3328596(1-14)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3328596
Zhu KZheng JYang ZDong J(2024)Identifying Rank-Happiness Maximizing Sets Under Group Fairness ConstraintsWeb and Big Data10.1007/978-981-97-7238-4_21(325-341)Online publication date: 28-Aug-2024
https://doi.org/10.1007/978-981-97-7238-4_21
Zheng JMa WWang YWang X(2023)Continuous $k$-Regret Minimization Queries: A Dynamic Coreset ApproachIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.316683535:6(5680-5694)Online publication date: 1-Jun-2023
https://doi.org/10.1109/TKDE.2022.3166835
Show More Cited By

Index Terms

K-Regret Queries Using Multiplicative Utility Functions
1. Information systems
  1. Information retrieval
    1. Retrieval models and ranking
      1. Top-k retrieval in databases
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Data structures and algorithms for data management
      2. Database query processing and optimization (theory)

Recommendations

Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality
SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data

Extracting interesting tuples from a large database is an important problem in multi-criteria decision making. Two representative queries were proposed in the literature: top- k queries and skyline queries. A top- k query requires users to specify their ...
Interactive regret minimization
SIGMOD '12: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data

We study the notion of regret ratio proposed in [19] Nanongkai et al. [VLDB10] to deal with multi-criteria decision making in database systems. The regret minimization query proposed in [19] Nanongkai et al. was shown to have features of both skyline ...
On hash functions using checksums

We analyse the security of iterated hash functions that compute an input dependent checksum which is processed as part of the hash computation. We show that a large class of such schemes, including those using non-linear or even one-way checksum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 43, Issue 2

Best of ICDT 2017 and Regular Papers

June 2018

154 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/3243648

Editor:
Christian S. Jensen
Aalborg University, Denmark

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 August 2018

Accepted: 01 May 2018

Revised: 01 April 2018

Received: 01 May 2017

Published in TODS Volume 43, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Australian Research Council

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
220
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zheng JMeng FWang YWang XWang SMa YHao Z(2024)Hybrid Regret Minimization: A Submodular ApproachIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3328596(1-14)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3328596
Zhu KZheng JYang ZDong J(2024)Identifying Rank-Happiness Maximizing Sets Under Group Fairness ConstraintsWeb and Big Data10.1007/978-981-97-7238-4_21(325-341)Online publication date: 28-Aug-2024
https://doi.org/10.1007/978-981-97-7238-4_21
Zheng JMa WWang YWang X(2023)Continuous $k$-Regret Minimization Queries: A Dynamic Coreset ApproachIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.316683535:6(5680-5694)Online publication date: 1-Jun-2023
https://doi.org/10.1109/TKDE.2022.3166835
Chen ZFu ALong CWu Y(2023)k-Pleased QueryingIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.313299235:4(4003-4017)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TKDE.2021.3132992
Hao ZZheng J(2023)Computing Online Average Happiness Maximization Sets over Data StreamsWeb and Big Data10.1007/978-3-031-25201-3_2(19-33)Online publication date: 10-Feb-2023
https://doi.org/10.1007/978-3-031-25201-3_2
Wang YLi YWong RTan K(2021)A Fully Dynamic Algorithm for k-Regret Minimizing Sets2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00144(1631-1642)Online publication date: Apr-2021
https://doi.org/10.1109/ICDE51399.2021.00144
Zheng JDong QWang XZhang YMa WMa Y(2021)Efficient processing of k-regret minimization queries with theoretical guaranteesInformation Sciences10.1016/j.ins.2021.11.080Online publication date: Dec-2021
https://doi.org/10.1016/j.ins.2021.11.080
Zheng JHuang XMa Y(2021)Efficient computation of deletion-robust k-coverage queriesKnowledge and Information Systems10.1007/s10115-020-01540-663:3(759-789)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s10115-020-01540-6
Ma WZheng JHao Z(2021)A Coreset Based Approach for Continuous k-regret Minimization Set Queries over Sliding WindowsWeb Information Systems and Applications10.1007/978-3-030-87571-8_5(49-61)Online publication date: 24-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-87571-8_5
Zheng JChen C(2020)Sorting-Based Interactive Regret MinimizationWeb and Big Data10.1007/978-3-030-60290-1_36(473-490)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1007/978-3-030-60290-1_36
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents