Matches in ScholarlyData for { <https://w3id.org/scholarlydata/inproceedings/www2012/paper/1168> ?p ?o. }
Showing items 1 to 14 of
14
with 100 items per page.
- 1168 creator ashish-goel.
- 1168 creator bahman-bahmani.
- 1168 type InProceedings.
- 1168 label "Partitioned Multi-Indexing: Algorithms, Analysis, and Applications to Social Search".
- 1168 sameAs 1168.
- 1168 abstract "In many social networking applications, specially with user generated content, it is desirable to give a higher ranking to content that is closer to the individual issuing the query. Queries occur at nodes in a network, documents are also created by nodes in the same network, and the goal is to find the document that matches the query and is closest in network distance to the node issuing the query. In this paper, we present the ``Partitioned Multi-Indexing'' scheme, which provides an approximate solution for this problem. Our scheme requires pre-processing time that is $\tilde{O}(m)$ where $m$ is the number of links in the network\footnote{The $\tilde{O}(m)$ notation hides factors that are poly-logarithmic in the $m$.}. After this pre-processing, our scheme allows for social index operations (i.e., social search queries, insertion of words into a document at any node, and deletion of words), all in time $\tilde{O}(1)$. Further, this scheme can be implemented to work on open source distributed streaming systems such as Yahoo! S4 or Twitter's Storm so that every social index operation takes $\tilde{O}(1)$ processing time and network queries in the worst case, and just two network queries in the common case where the reverse index corresponding to the query keyword is much smaller than the memory available at any distributed compute node. Our scheme builds upon an approximate distance oracle of Das Sarma et al. \cite{DasSarma10}. The worst-case approximation ratio of our scheme is $\tilde{O}(1)$ for undirected networks; our simulations on the social network Twitter as well as synthetic networks show that in practice, the approximation ratio is actually close to 1 for both directed and undirected networks. We believe that this work is the first demonstration of the feasibility of social search with real-time text updates at large scales.".
- 1168 hasAuthorList authorList.
- 1168 isPartOf proceedings.
- 1168 keyword "Distributed Streaming".
- 1168 keyword "Massive Scale".
- 1168 keyword "Real Time".
- 1168 keyword "Social Search".
- 1168 keyword "Strong theoretical efficiency and quality guarantees".
- 1168 title "Partitioned Multi-Indexing: Algorithms, Analysis, and Applications to Social Search".