Comprehensive coverage of the public web is crucial to web search engines. Search engines use crawlers to retrieve pages and then discover new ones by extracting the pages' outgoing links. However, the set of pages reachable from the publicly linked web is estimated to be significantly smaller than the invisible web, the set of documents that have no incoming links and can only be retrieved through web applications and web forms. The Sitemaps protocol is a fast-growing web protocol supported jointly by major search engines to help content creators and search engines unlock this hidden data by making it available to search engines. In this paper, we perform a detailed study of how "classic" discovery crawling compares with Sitemaps, in key measures such as coverage and freshness over key representative websites as well as over billions of URLs seen at Google. We observe that Sitemaps and discovery crawling complement each other very well, and offer different tradeoffs.

With the growing acceptance of the Internet as a new dissemination medium, several new and interesting challenges arise in building a digital commerce infrastructure. We discuss some of the issues that arise in building such an infrastructure. In particular, we study how one can find and pay for digital information, and how one can safeguard the information from invalid access and duplication. We use examples from our Stanford Digital Library Project to illustrate some of these problems and their potential solutions.

In many applications, new data is being generated every day. Often an index of the data of a past window of days is required to answer queries efficiently. For example, in a warehouse one may need an index on the sales records of the last week for efficient data mining, or in a Web service one may provide an index of Netnews articles of the past month. In this paper, we propose a variety of wave indices where the data of a new day can be efficiently added, and old data can be quickly expired, to maintain the required window. We compare these schemes based on several system performance measures, such as storage, query response time, and maintenance work, as well as on their simplicity and ease of coding.

We consider the problem of managing the information required to locate users in a wireless communication system, with a focus on designing and evaluating location management techniques that are efficient, scalable, and flexible. The three key contributions of this paper are: (1) A family of location management techniques, HiPER (for Hierarchical ProfilE Replication), that efficiently provide life-long (non-geographic) numbering with fast location lookup; (2) Pleiades, a scalable event-driven wireless system simulator with realistic calling and mobility patterns derived from several months of real traffic traces; and (3) multi-day simulations comparing our proposed location management techniques with current and previously proposed techniques on a realistic geographical and network topology. Research supported by the Center for Telecommunications and the Center for Integrated Systems at Stanford University, and by equipment grants from Digital and IBM Corporations. 1 Introduction I...

In this paper, we study the area-balanced multiway partitioning problem of VLSI circuits based on a new dual netlist representation named the hybrid dual netlist (HDN), and propose a general paradigm for multiway circuit partitioning based on dual net transformation. Given a netlist, we first compute a K-way partitioning of nets based on the HDN representation, and then transform the K-way net partition into a K-way module partitioning solution. The main contribution of our paper is in the formulation and solution of the K-way module contention (KMC) problem, which determines the best assignment of the modules in contention to partitions while maintaining user-specified area requirements when we transform the net partition into a module partition. Under a natural definition of binding function between nets and modules, and preference function between partitions and modules, we show that the K-MC problem can be reduced to a min-cost max-flow problem. We present an efficient solution to the K-MC problem based on network flow computation. We apply our dual transformation paradigm to the well-known K-way Fiduccia-Mattheyses (FM) partitioning algorithm (K-FM) and show that the new algorithm, named K-DualFM, reduces the net cutsize by 20% to 31% compared with the K-FM algorithm. We also apply the same paradigm to the K-maximum fanout-free cone (MFFC)-FM algorithm, a K-FM algorithm based on MFFC clustering, and show that the resulting algorithm, K-DualMFFC-FM reduces the net cutsize by 15% to 26% compared with K-MFFC-FM. Furthermore, we compare the K-DualFM algorithm with EIG1 and Paraboli, two recently proposed spectral-based bipartitioning algorithms. We showed that K-DualFM reduces the net cutsize by 56% on average when compared with EIG1 and produces comparable results with Paraboli.

We consider per-user profile replication as a mechanism for faster location lookup of mobile users in a Personal Communications Service system. We present a minimum-cost maximum-flow based algorithm to compute the set of sites at which a user profile should be replicated given known calling and user mobility patterns. We then present schemes for replication plans that gracefully adapt to changes in the calling and mobility patterns. 1 Introduction In a Personal Communications Service (PCS) system, users place and receive calls through a wireless medium. Calls may deliver voice, data, text, facsimile, or video information [JLLM94]. PCS users are located in system-defined cells, which are bounded geographical areas. When a user places a call, the PCS infrastructure must route the call to the base-station located in the same cell as the callee. The base-station then transmits the data in the call to the PCS unit through the wireless medium. We consider the problem of locating users who...