More Web Proxy on the site http://driver.im/

research-article

Query Answering Efficiency in Expert Networks Under Decentralized Search

Authors:

Mudhakar Srivatsa,

Derya Cansever,

Michelle VanniAuthors Info & Claims

CIKM '16: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management

Pages 2119 - 2124

https://doi.org/10.1145/2983323.2983652

Published: 24 October 2016 Publication History

Abstract

Expert networks are formed by a group of expert-profes\-sionals with different specialties to collaboratively resolve specific queries. In such networks, when a query reaches an expert who does not have sufficient expertise, this query needs to be routed to other experts for further processing until it is completely solved; therefore, query answering efficiency is sensitive to the underlying query routing mechanism being used. Among all possible query routing mechanisms, decentralized search, operating purely on each expert's local information without any knowledge of network global structure, represents the most basic and scalable routing mechanism. However, there is still a lack of fundamental understanding of the efficiency of decentralized search in expert networks. In this regard, we investigate decentralized search by quantifying its performance under a variety of network settings. Our key findings reveal the existence of network conditions, under which decentralized search can achieve significantly short query routing paths (i.e., between O(log n) and O(log² n) hops, n: total number of experts in the network). Based on such theoretical foundation, we then study how the unique properties of decentralized search in expert networks is related to the anecdotal small-world phenomenon. To the best of our knowledge, this is the first work studying fundamental behaviors of decentralized search in expert networks. The developed performance bounds, confirmed by real datasets, can assist in predicting network performance and designing complex expert networks.

References

[1]

K. Balog, L. Azzopardi, and M. De Rijke, "Formal models for expert finding in enterprise corpora," in ACM SIGIR, 2006.

Digital Library

[2]

P. Serdyukov, H. Rode, and D. Hiemstra, "Modeling multi-step relevance propagation for expert finding," in ACM CIKM, 2008.

Digital Library

[3]

Q. Shao, Y. Chen, S. Tao, X. Yan, and N. Anerousis, "Efficient ticket routing by resolution sequence mining," in ACM SIGKDD, 2008.

Digital Library

[4]

H. Zhang, E. Horvitz, Y. Chen, and D. C. Parkes, "Task routing for prediction tasks," in AAMAS, 2012.

Digital Library

[5]

G. Miao, L. E. Moser, X. Yan, S. Tao, Y. Chen, and N. Anerousis, "Generative models for ticket resolution in expert networks," in ACM SIGKDD, 2010.

Digital Library

[6]

A. Banerjee and S. Basu, "A social query model for decentralized search," in ACM SNAKDD, 2008.

[7]

J. Kleinberg and P. Raghavan, "Query incentive networks," in IEEE FOCS, 2005.

Digital Library

[8]

J. Zeng and W. Hsu, "Optimal routing in a small-world network," Journal of Computer Science & Technology, vol. 21, pp. 476--481, 2006.

[9]

H. Sun, M. Srivatsa, S. Tan, Y. Li, L. M. Kaplan, S. Tao, and X. Yan, "Analyzing expert behaviors in collaborative networks," in ACM SIGKDD, 2014.

Digital Library

[10]

B. Bollobás and F. D. L. Vega, "The diameter of random regular graphs," Combinatorica, vol. 2, pp. 125--134, 1982.

[11]

D. J. Watts and S. H. Strogatz, "Collective dynamics of 'small-world' networks," Nature, vol. 393, pp. 440--442, 1998.

[12]

M. Draief and A. Ganesh, "Efficient routeing in poisson small-world networks," Journal of Applied Probability, pp. 678--686, 2006.

[13]

L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman, "Search in power-law networks," Phys. Rev. E, vol. 64, p. 046135, 2001.

[14]

S. Milgram, "The small world problem," Psychology Today, vol. 67, pp. 61--67, 1967.

[15]

J. Travers and S. Milgram, "An experimental study of the small world problem," Sociometry, vol. 32, pp. 425--443, 1969.

[16]

C. Korte and S. Milgram, "Acquaintance networks between racial groups: Application of the small world method," Journal of Personality and Social Psychology, vol. 15, pp. 101--108, 1970.

[17]

J. Guare, Six Degrees of Separation: A Play. Vintage Books, 1990.

[18]

J. Kleinberg, "The small-world phenomenon: An algorithmic perspective," in ACM STOC, 2000.

Digital Library

[19]

L. Ma, "Query answering via decentralized search," Technical Report, IBM T. J. Watson Research Center, Yorktown, NY, USA, Jul 2016. {Online}. Available: http://researcher.ibm.com/researcher/files/us-maliang/QueryRoutingTR.pdf

[20]

J. Kleinberg, "Complex networks and decentralized search algorithms," in International Congress of Mathematicians, 2006.

Cited By

Han JSun A(2020)DeepRouting: A Deep Neural Network Approach for Ticket Routing in Expert Network2020 IEEE International Conference on Services Computing (SCC)10.1109/SCC49832.2020.00057(386-393)Online publication date: Nov-2020
https://doi.org/10.1109/SCC49832.2020.00057
Han JSun A(2017)Mean Average Distance to Resolver: An Evaluation Metric for Ticket Routing in Expert Network2017 IEEE International Conference on Software Maintenance and Evolution (ICSME)10.1109/ICSME.2017.18(594-602)Online publication date: Sep-2017
https://doi.org/10.1109/ICSME.2017.18

Index Terms

Query Answering Efficiency in Expert Networks Under Decentralized Search

Recommendations

Performance Bounds of Decentralized Search in Expert Networks for Query Answering

Expert networks are formed by a group of expert-professionals with different specialties to collaboratively resolve specific queries posted to the network. In such networks, when a query reaches an expert who does not have sufficient expertise, this ...
Weight-based consistent query answering over inconsistent $${\mathcal {SHIQ}}$$ knowledge bases

Non-standard query mechanisms that work under inconsistency are required in some important description logic (DL)-based applications, including those involving an inconsistent DL knowledge base ( KB) whose intensional knowledge is consistent but is ...
Reformulation-Based Query Answering for RDF Graphs with RDFS Ontologies
The Semantic Web
Abstract
Query answering in RDF knowledge bases has traditionally been performed either through graph saturation, i.e., adding all implicit triples to the graph, or through query reformulation, i.e., modifying the query to look for the explicit triples ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '16: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management

October 2016

2566 pages

ISBN:9781450340731

DOI:10.1145/2983323

General Chairs:
Snehasis Mukhopadhyay
Indiana University Purdue University Indianapolis, USA
,
ChengXiang Zhai
University of Illinois at Urbana-Champaign, USA
,
Program Chairs:
Elisa Bertino
Purdue University
,
Fabio Crestani
University of Lugano
,
Javed Mostafa
University of North Carolina
,
Jie Tang
Tsinghua University
,
Luo Si
Alibaba Group Inc & Purdue University
,
Xiaofang Zhou
University of Queensland
,
Yi Chang
Yahoo Research
,
Yunyao Li
IBM Research - Almaden
,
Parikshit Sondhi
WalmartLabs

Copyright © 2016 ACM.

© 2016 Association for Computing Machinery. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of the United States government. As such, the United States Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 October 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

ARL Network Science CTA

Conference

CIKM'16

Sponsor:

CIKM'16: ACM Conference on Information and Knowledge Management

October 24 - 28, 2016

Indiana, Indianapolis, USA

Acceptance Rates

CIKM '16 Paper Acceptance Rate 160 of 701 submissions, 23%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
173
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Han JSun A(2020)DeepRouting: A Deep Neural Network Approach for Ticket Routing in Expert Network2020 IEEE International Conference on Services Computing (SCC)10.1109/SCC49832.2020.00057(386-393)Online publication date: Nov-2020
https://doi.org/10.1109/SCC49832.2020.00057
Han JSun A(2017)Mean Average Distance to Resolver: An Evaluation Metric for Ticket Routing in Expert Network2017 IEEE International Conference on Software Maintenance and Evolution (ICSME)10.1109/ICSME.2017.18(594-602)Online publication date: Sep-2017
https://doi.org/10.1109/ICSME.2017.18

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents