We consider two types of searching models, where the goal is to design an adaptive algorithm that locates an unknown vertex in a graph by repeatedly performing queries. In the vertex-query model, each query points to a vertex @math and the response either admits that @math is the target or provides a neighbor of @math on a shortest path from @math to the target. This model has been introduced for trees by Onak and Parys [FOCS 2006] and by Emamjomeh- [STOC 2016] for arbitrary graphs. In the edge-query model, each query chooses an edge and the response reveals which endpoint of the edge is closer to the target, breaking ties arbitrarily. Our goal is to analyze solutions to these problems assuming that some responses may be erroneous. We develop a scheme for tackling such noisy models with the following line of arguments: For each of the two models, we analyze a generic strategy that assumes a fixed number of lies and give a precise bound for its length via an amortized analysis. From this, we derive bounds for both a linearly bounded error rate, where the number of errors in @math queries is bounded by @math for some @math , and a probabilistic model in which each response is incorrect with some probability @math . The bounds for adversarial case turn out to be strong enough for non-adversarial scenarios as well. We obtain thus a much simpler strategy performing fewer vertex-queries than one by Emamjomeh- [STOC 2016]. For edge-queries, not studied before for general graphs, we obtain bounds that are tight up to @math factors in all error models. Applying our graph-theoretic results to the setting of edge-queries for paths, we obtain a number of improvements over existing bounds for searching in a sorted array in the presence of errors, including an exponential improvement for the prefix-bounded model in unbounded domains.
Regarding the problem of searching in graphs without errors, many papers have been devoted to trees, mainly because it is a structure that naturally generalizes paths, which represents the classical binary search (see e.g. @cite_3 for search in a path with non-uniform query times). This query model in case of trees is equivalent to several other problems, including vertex ranking @cite_4 or tree-depth @cite_19 . There exist linear-time algorithms for finding optimal query strategies @cite_13 @cite_38 . A lot of effort has been done to understand the complexity for trees with non-uniform query times. It turns out that the problem becomes hard for trees @cite_14 @cite_31 . Also refer the reader to works on a closely related query game with edge queries @cite_10 @cite_32 @cite_16 @cite_8 @cite_36 . For general graphs, a strategy that always queries a 1-median (the minimizer of the sum of distances over all vertices) has length at most @math @cite_26 .
@cite_38 @cite_14 @cite_4 @cite_26 @cite_8 @cite_36 @cite_10 @cite_32 @cite_3 @cite_19 @cite_31 @cite_16 @cite_13
2092864936 2009372021 2064883689 2395495808 1985996385 2062785505 2004158059 2293258084 2014544956 2052210031 2593445670 1975968324 1991217335
Abstract Documents in computer-readable form can be used to provide information about other documents, i.e. those they cite. To do this efficiently requires procedures for computer recognition of citing statements. This is not easy, especially for multi-sentence citing statements. Computer recognition procedures have been developed which are accurate to the following extent: 73 of the words in statements selected by computer procedures as being citing statements are words which are correctly attributable to the corresponding documents. The retrieval effectiveness of computer-recognized citing statements was tested in the following way. First, for eight retrieval requests in inorganiic chemistry, average recall by search of Chemical Abstracts Service indexing and Chemical Abstracts abstract text words was found to be 50 . Words from citing statements referring to the papers to be retrieved were then added to the index terms and abstract words as additional access points, and searching was repeated. Average recall increased to 70 . Only words from citing statements published within a year of the cited papers were used. The retrieval effect of citing statement words alone (published within a year) without index or abstract terms was the following: average recall was 40 . When just the words of the titles of the cited papers were added to those citing statement words, average recall increased to 50 . Purpose – The purpose of this paper is to suggest an alternative to the widely used Times Cited criterion for analysing citation networks. The approach involves taking account of the natures of the papers that cite a given paper, so as to differentiate between papers that attract the same number of citations.Design methodology approach – ArticleRank is an algorithm that has been derived from Google's PageRank algorithm to measure the influence of journal articles. ArticleRank is applied to two datasets – a citation network based on an early paper on webometrics, and a self‐citation network based on the 19 most cited papers in the Journal of Documentation – using citation data taken from the Web of Knowledge database.Findings – ArticleRank values provide a different ranking of a set of papers from that provided by the corresponding Times Cited values, and overcomes the inability of the latter to differentiate between papers with the same numbers of citations. The difference in rankings between Times Cited ... A citing sentence is one that appears in a scientific article and cites previous work. Citing sentences have been studied and used in many applications. For example, they have been used in scientific paper summarization, automatic survey generation, paraphrase identification, and citation function classification. Citing sentences that cite multiple papers are common in scientific writing. This observation should be taken into consideration when using citing sentences in applications. For instance, when a citing sentence is used in a summary of a scientific paper, only the fragments of the sentence that are relevant to the summarized paper should be included in the summary. In this paper, we present and compare three different approaches for identifying the fragments of a citing sentence that are related to a given target reference. Our methods are: word classification, sequence labeling, and segment classification. Our experiments show that segment classification achieves the best results. Scholars are increasingly citing electronic “web references” which are not preserved in libraries or full text archives. WebCite is a new standard for citing web references. To “webcite” a document involves archiving the cited Web page through www.webcitation.org and citing the WebCite permalink instead of (or in addition to) the unstable live Web page. This journal has amended its “instructions for authors” accordingly, asking authors to archive cited Web pages before submitting a manuscript. Almost 200 other journals are already using the system. We discuss the rationale for WebCite, its technology, and how scholars, editors, and publishers can benefit from the service. Citing scholars initiate an archiving process of all cited Web references, ideally before they submit a manuscript. Authors of online documents and websites which are expected to be cited by others can ensure that their work is permanently available by creating an archived copy using WebCite and providing the citation information including the WebCite link on their Web document(s). Editors should ask their authors to cache all cited Web addresses (Uniform Resource Locators, or URLs) “prospectively” before submitting their manuscripts to their journal. Editors and publishers should also instruct their copyeditors to cache cited Web material if the author has not done so already. Finally, WebCite can process publisher submitted “citing articles” (submitted for example as eXtensible Markup Language [XML] documents) to automatically archive all cited Web pages shortly before or on publication. Finally, WebCite can act as a focussed crawler, caching retrospectively references of already published articles. Copyright issues are addressed by honouring respective Internet standards (robot exclusion files, no-cache and no-archive tags). Long-term preservation is ensured by agreements with libraries and digital preservation organizations. The resulting WebCite Index may also have applications for research assessment exercises, being able to measure the impact of Web services and published Web documents through access and Web citation metrics. @PARASPLIT [J Med Internet Res 2005;7(5):e60]