waashk/dblp huggingface dataset:
edsc: efficient density-based subspace clustering. subspace clustering mines clusters hidden in subspaces of high-dimensional data sets. density-based approaches have been shown to successfully mine clusters of arbitrary shape even in the presence of noise in full space clustering. exhaustive search of all density-based subspace clusters, however, results in infeasible runtimes for large high-dimensional data sets. this is due to the exponential number of possible subspace projections in addition to the high computational cost of density-based clustering. in this paper, we propose lossless efficient detection of density-based subspace clusters. in our edsc (efficient density-based subspace clustering) algorithm we reduce the high computational cost of density-based subspace clustering by a complete multistep filter-and-refine algorithm. our first hypercube filter step avoids exhaustive search of all regions in all subspaces by enclosing potentially density-based clusters in hypercubes. our second filter step provides additional pruning based on a density monotonicity property. in the final refinement step, the exact unbiased density-based subspace clustering result is detected. as we prove that pruning is lossless in both filter steps, we guarantee completeness of the result. in thorough experiments on synthetic and real world data sets, we demonstrate substantial efficiency gains. our lossless edsc approach outperforms existing density-based subspace clustering algorithms by orders of magnitude.
probabilistic polyadic factorization and its application to personalized recommendation. multiple-dimensional, i.e., polyadic, data exist in many applications, such as personalized recommendation and multiple-dimensional data summarization. analyzing all the dimensions of polyadic data in a principled way is a challenging research problem. most existing methods separately analyze the marginal relationships among pairwise dimensions and then combine the results afterwards. motivated by the fact that various dimensions of polyadic data jointly affect each other, we propose a probabilistic polyadic factorization approach to directly model all the dimensions simultaneously in a unified framework. we then show the connection between the probabilistic polyadic factorization and a non-negative version of the tucker tensor factorization. we provide detailed theoretical analysis of the new modeling framework, discuss implementation techniques for our models, and propose several extensions to the basic framework. we then apply the proposed models to the application of personalized recommendation. extensive experiments on a social bookmarking dataset, delicious, and a paper citation dataset, citeseer, demonstrate the effectiveness of the proposed models.
rewriting of visibly pushdown languages for xml data integration. in this paper, we focus on xml data integration by studying rewritings of xml target schemas in terms of source schemas. rewriting is very important in data integration systems where the system is asked to find and assemble xml documents from the data sources and produce documents which satisfy a target schema. as schema representation, we consider visibly pushdown automata (vpas) which accept visibly pushdown languages (vpls). the latter have been shown to coincide with the family of (word-encoded) regular tree languages which are the basis of formalisms for specifying xml schemas. furthermore, practical semi-formal xml schema specifications (defined by simple pattern conditions on xml) compile into vpas which are exponentially more concise than other representations based on tree automata. notably, vpls enjoy a "well-behavedness" which facilitates us in addressing rewriting problems for xml data integration. based on vpas, we positively solve these problems, and present detailed complexity analyses.
vanity fair: privacy in querylog bundles. a recently proposed approach to address privacy concerns in storing web search querylogs is bundling logs of multiple users together. in this work we investigate privacy leaks that are possible even when querylogs from multiple users are bundled together, without any user or session identifiers. we begin by quantifying users' propensity to issue own-name vanity queries and geographically revealing queries. we show that these propensities interact badly with two forms of vulnerabilities in the bundling scheme. first, structural vulnerabilities arise due to properties of the heavy tail of the user search frequency distribution, or the distribution of locations that appear within a user's queries. these heavy tails may cause a user to appear visibly different from other users in the same bundle. second, we demonstrate analytical vulnerabilities based on the ability to separate the queries in a bundle into threads corresponding to individual users. these vulnerabilities raise privacy issues suggesting that bundling must be handled with great care.
an automatic approach to construct domain-specific web portals. we describe the architecture of an automatic domain-specific web portal construction system. the system has three major components: i) a focused crawler that collects the domain-specific pages on the web, ii) an information extraction engine that extracts useful fields from these web pages, and iii) a query engine that allows both typical keyword based queries on the pages and advanced queries on the extracted data fields. we present a prototype system that works for the course homepages domain on the web. a user study with the prototype system shows that our approach produces high quality results and achieves better precision figures than the typical keyword based search.
just-in-time contextual advertising. contextual advertising is a type of web advertising, which, given the url of a web page, aims to embed into the page (typically via javascript) the most relevant textual ads available. for static pages that are displayed repeatedly, the matching of ads can be based on prior analysis of their entire content; however, ads need to be matched also to new or dynamically created pages that cannot be processed ahead of time. analyzing the entire body of such pages on-the-fly entails prohibitive communication and latency costs. to solve the three-horned dilemma of either low-relevance or high-latency or high-load, we propose to use text summarization techniques paired with external knowledge (exogenous to the page) to craft short page summaries in real time. empirical evaluation proves that matching ads on the basis of such summaries does not sacrifice relevance, and is competitive with matching based on the entire page content. specifically, we found that analyzing a carefully selected 5% fraction of the page text sacrifices only 1%-3% in ad relevance. furthermore, our summaries are fully compatible with the standard javascript mechanisms used for ad placement: they can be produced at ad-display time by simple additions to the usual script, and they only add 500-600 bytes to the usual request.
inferring document relevance from incomplete information. recent work has shown that average precision can be accurately estimated from a small random sample of judged documents. unfortunately, such "random pools" cannot be used to evaluate retrieval measures in any standard way. in this work, we show that given such estimates of average precision, one can accurately infer the relevances of the remaining unjudged documents, thus obtaining a fully judged pool that can be used in standard ways for system evaluation of all kinds. using trec data, we demonstrate that our inferred judged pools are well correlated with assessor judgments, and we further demonstrate that our inferred pools can be used to accurately infer precision recall curves and all commonly used measures of retrieval performance.
merging distributed database summaries. the database summarization system coined s<scp>aint</scp>e<scp>ti</scp>q provides multi-resolution summaries of structured data stored into acentralized database. summaries are computed online with a conceptual hierarchical clustering algorithm. however, most companies work in distributed legacy environments and consequently the current centralized version of s<scp>aint</scp>e<scp>ti</scp>q is either not feasible (privacy preserving) or not desirable (resource limitations). to address this problem, we propose new algorithms to generate a single summary hierarchy given two distinct hierarchies, without scanning the raw data. the greedy merging algorithm (gma) takes all leaves of both hierarchies and generates the optimal partitioning for the considered data set with regards to a cost function (compactness and separation). then, a hierarchical organization of summaries is built by agglomerating or dividing clusters such that the cost function may emphasize local or global patterns in the data. thus, we obtain two different hierarchies according to the performed optimisation. however, this approach breaks down due to its exponential time complexity. two alternative approaches with constant time complexity w.r.t. the number of data items, are proposed to tackle this problem. the first one, called merge by incorporation algorithm (mia), relies on the s<scp>aint</scp>e<scp>ti</scp>q engine whereas the second approach, named merge by alignment algorithm (maa), consists in rearranging summaries by levels in a top-down manner. then, we compare those approaches using an original quality measure in order to quantify how good our merged hierarchies are. finally, an experimental study, using real data sets, shows that merging processes (mia and maa) are efficient in terms of computational time.
efficient evaluation of high-selective xml twig patterns with parent child edges in tree-unaware rdbms. recent study showed that native twig join algorithms and tree-aware relational framework significantly outperform tree-unaware approaches in evaluating structural relationships in xml twig queries. in this paper, we present an efficient strategy to evaluate high-selective twig queries containing only parent-child relationships in a tree-unaware relational environment. our scheme is built on top of our s<scp>ucxent</scp>++ system. we show that by exploiting the encoding scheme of s<scp>ucxent</scp>++, we can devise efficient strategy for evaluating such twig queries. extensive performance studies on various data sets and queries show that our approach performs better than a representative tree-unaware approach (g<scp>lobal</scp>-o<scp>rder</scp>) and a state-of-the-art native twig join algorithm (tjf<scp>ast</scp>) on all benchmark queries with the highest observed gain factors being 243 and 95, respectively. additionally, our approach reduces significantly the performance gap between tree-aware and tree-unaware approaches and even outperforms a tree-aware approach(m<scp>onet</scp>db/xq<scp>uery</scp>) for certain high-selective twig queries. we also report our insights to the plan choices a relational optimizer made during twig query evaluation by visually characterizing its behavior over the relational selectivity space.
structure and semantics for expressive text kernels. several text categorization applications require a representation beyond the standard bag-of-words paradigm. kernel-based learning has approached this problem by (i) considering information about syntactic structure or by (ii) incorporating knowledge about the semantic similarity of term features. we propose a generalized framework consisting of a family of kernels that jointly incorporate syntactic and semantic similarity and demonstrate the power of this approach in a series of experiments.
external perfect hashing for very large key sets. we present a simple and efficient external perfect hashing scheme (referred to as eph algorithm) for very large static key sets. we use a number of techniques from the literature to obtain a novel scheme that is theoretically well-understood and at the same time achieves an order-of-magnitude increase in the size of the problem to be solved compared to previous "practical" methods. we demonstrate the scalability of our algorithm by constructing minimum perfect hash functions for a set of 1.024 billion urls from the world wide web of average length 64 characters in approximately 62 minutes, using a commodity pc. our scheme produces minimal perfect hash functions using approximately 3.8 bits per key. for perfect hash functions in the range {0,...,2n - 1} the space usage drops to approximately 2.7 bits per key. the main contribution is the first algorithm that has experimentally proven practicality for sets in the order of billions of keys and has time and space usage carefully analyzed without unrealistic assumptions.
conceptual modeling by analogy and metaphor. metaphor is not merely a rhetorical device, characteristic of language alone, but rather a fundamental feature of the human conceptual system. a metaphor is understood by finding an analogy mapping between two domains. this paper argues that analogy mappings facilitate conceptual modeling by allowing the designer to reinterpret fragments of familiar conceptual models in other contexts. the contributions of the paper are expressed within the tradition of the entity-relation model.
self-correcting queries for xml. it has been observed that queries over xml data sources are often unsatisfiable. unsatisfiability may stem from several different sources, e.g., the user may be insufficiently familiar with the labels appearing the documents, or may not be intimately aware of the hierarchical structure of the documents. this difficulty may be compounded by the fact that errors in query formulation lead to an empty answer, and not to some sort of compilation error. to deal with query and document mismatches, previous research has considered returning answers that maximally satisfy (in some sense) the query, instead of only returning strictly satisfying answers. however, this breaks the golden database rule that only strictly satisfying answers are returned when querying. indeed, the relationship between the query and answers is no longer clear, when unsatisfying answers are returned. to revive the golden database rule, this paper proposes a framework for deriving self-correcting queries over xml. this framework generates similar satisfiable queries, when the user query is unsatisfiable. the user can then choose a satisfiable query of interest, and receive exactly satisfying answers to this query.
leveraging context in user-centric entity detection systems. a user-centric entity detection system is one in which the primary consumer of the detected entities is a person who can perform actions on the detected entities (e.g. perform a search, view a map, shop, etc.). we contrast this with machine-centric detection systems where the primary consumer of the detected entities is a machine. machine-centric detection systems typically focus on the quantity of detected entities, measured by precision and recall metrics, with the goal of correctly identifying every single entity in a document. however, the simple precision/recall scores of machine-centric entity detection systems fail to accurately reflect the quality of detected entities in user-centric systems, where users may not necessarily want to "see" every possible entity. we posit that not all of the detected entities in a given piece of text are necessarily relevant to the main topic of the text, nor are they necessarily interesting enough to the user to warrant further action. in fact, presenting all of the detected entities to a user may annoy the user to the point where he decides to turn this capability off completely, an undesirable outcome. therefore, we propose to measure the quality and utility of user-centric entity detection systems in three core dimensions: the accuracy, the interestingness, and the relevance of the entities it presents to the user. we show that leveraging surrounding context can greatly improve the performance of such systems in all three dimensions by employing novel algorithms for generating a concept vector and for finding concept extensions using search query logs. we extensively evaluate the proposed algorithms within contextual shortcuts - a large-scale user-centric entity detection platform - using 1,586 entities detected over 1,519 documents. the results confirm the importance of using context within user-centric entity detection systems, and validate the usefulness of the proposed algorithms by showing how they improve the overall entity detection quality within contextual shortcuts.
extending query translation to cross-language query expansion with markov chain models. dictionary-based approaches to query translation have been widely used in cross-language information retrieval (clir) experiments. however, translation has been not only limited by the coverage of the dictionary, but also affected by translation ambiguities. in this paper we propose a novel method of query translation that combines other types of term relation to complement the dictionary-based translation. this allows extending the literal query translation to related words, which produce a beneficial effect of query expansion in clir. in this paper, we model query translation by markov chains (mc), where query translation is viewed as a process of expanding query terms to their semantically similar terms in a different language. in mc, terms and their relationships are modeled as a directed graph, and query translation is performed as a random walk in the graph, which propagates probabilities to related terms. this framework allows us to incorporating different types of term relation, either between two languages or within the source or target languages. in addition, the iterative training process of mc allows us to attribute higher probabilities to the target terms more related to the original query, thus offers a solution to the translation ambiguity problem. we evaluated our method on three clir benchmark collections, and obtained significant improvements over traditional dictionary-based approaches.
a fast unified optimal route query evaluation algorithm. we investigate the problem of how to evaluate, fast and efficiently, classes of optimal route queries on a massive graph in a unified framework. to evaluate a route query effectively, a large network is partitioned into a collection of fragments, and distances of some optimal routes in the network are pre-computed. under such a setting, we find a unified algorithm that can evaluate classes of optimal route queries. the classes that can be processed efficiently are called constraint preserving (cp) which include, among others, shortest path, forbidden edges, forbidden nodes and α-autonomy optimal route query classes. we prove the correctness of the unified algorithm. we then turn our attention to the optimization of the proposed algorithm. several pruning and optimization techniques are derived that minimize the search time and i/o accesses. we show empirically that these techniques are effective. the proposed optimal route query evaluation algorithm, with all these techniques incorporated, is compared with a main-memory and a disk-based brute-force cp algorithms. we show experimentally that the proposed unified algorithm outperforms the brute-force algorithms, both in term of cpu time and i/o cost, by a wide margin.
domain knowledge conceptual inter-media indexing: application to multilingual multimedia medical reports. conceptual indexing is a way to produce only one index for many multilingual documents. inter-media conceptual indexing promotes the use of common concepts between two media in order to use a single index for several media. in this paper we explore such an advance indexing point of view. we show the benefit of an automatic conceptual indexing for texts and its extension for text and image documents. tests are conducted on the multilingual image and text medical document corpus of the clef initiative, where we obtain best results on text in 2005 and 2006, and show promising results on images, and best results for the combination of image and text.
an experimental study of the impact of information extraction accuracy on semantic search performance. researchers have shown that various natural language processing techniques can be used in document analysis to impact search performance. for the most part, they examined how an analysis system with certain performance characteristics can be leveraged to improve document and/or passage search results. we have previously shown that semantic queries which utilize named entity and relation information extracted from the corpus can lead to significant improvement in search performance. in this paper, we extend our previous efforts and examine how search performance degrades in the face of imperfect named entity and relation extraction. our study was carried out by developing gold standard annotated corpora and applying different error models to the gold standard annotations to simulate errors made by automatic recognizers. we identify automatic recognizer characteristics that make them more amenable to our search tasks, show that recognizer recall has more significant impact on semantic search performance than its precision, and demonstrate that significant improvement in both map and exact precision scores can be achieved by adopting automatic named entity and relation recognizers with near state-of-the-art performance.
the t4sql temporal query language. time characterizes every aspect of our life and its management when storing and querying data is very important. in this paper we propose a new temporal query language, called t4sql, supporting multiple temporal dimensions of data. besides the well-known valid and transaction times, it encompasses two additional temporal dimensions, namely, availability and event times. the availability time records when information is known and treated as true by the information system; the event times record the occurrence times of both the event that starts the valid time and the event that ends it. t4sql is capable to deal with different temporal semantics (atemporal aka non-sequenced, current, sequenced, next) with respect to every temporal dimension. moreover, t4sql provides a novel temporal grouping clause and an orthogonal management of temporal properties when defining the selection condition(s) and the schema for the output relation.
discovering interesting usage patterns in text collections: integrating text mining with visualization. this paper addresses the problem of making text mining results more comprehensible to humanities scholars, journalists, intelligence analysts, and other researchers, in order to support the analysis of text collections. our system, featurelens1, visualizes a text collection at several levels of granularity and enables users to explore interesting text patterns. the current implementation focuses on frequent itemsets of n-grams, as they capture the repetition of exact or similar expressions in the collection. users can find meaningful co-occurrences of text patterns by visualizing them within and across documents in the collection. this also permits users to identify the temporal evolution of usage such as increasing, decreasing or sudden appearance of text patterns. the interface could be used to explore other text features as well. initial studies suggest that featurelens helped a literary scholar and 8 users generate new hypotheses and interesting insights using 2 text collections.