Evolution: Google vs. DRIS

This paper gives an absolute new search system that builds the information retrieval infrastructure for Internet. Now most search engine companies are mainly concerned with how to make profit from company users by advertisement and ranking prominence, but never consider what its real customers will feel. Few web search engines can sell billions dollars just at the cost of inconvenience of most Internet users, but not its high quality of search service. When we have to bear the bothersome advertisements in the awful results and have no choices, Internet as the kind of public good will surely be undermined. If current Internet can't fully ensure our right to know, it may need some sound improvements or a revolution.

2 metadata harvest system (Fig.2). When we need to integrate different kinds of information resource, we can harvest the metadata from sub databases and build a union metadata database to provide the combined search function. Normally Metadata is much smaller than data itself, for example, a video record is 1GB but its metadata may be only 1kB. Some systems based on OAI like NSDL just apply this method. Figure 2 in information retrieval system based on metadata harvest architecture, the metadata of sub databases will be timely downloaded by a harvest mechanism. Users can obtain different kinds of information from a union metadata database. 3 Distributed search system (Fig.3). If the data sources are large enough and the aggregation of Metadata is also too huge to store in a system, we can use distributed frame to integrate all the resources. Distributed search system hasn't any actual data resources, but an index that descript the search interface and other characters of its sub data resources. Different resources will cooperate to carry out the user's query. InfoBus (3 ) Collection description database User Figure 3 distributed information retrieval system has no his own actual record database. When receiving a query from a user, it will instantly obtain the records through the search interfaces provided by sub databases.

how to select correct architecture
There are two main characters to determine the architecture of a information retrieval system, the size and diversity of data source. We can select appreciate appropriate according to the principle shown in Fig.4.

Figure4 the principle about how to select correct architecture
Internet is the biggest database in this world. We can't use a single kind of search system to manage this database. But most web search engines only apply the centralized structure. Some limitations of current web search system have been very obvious. So how to correctly apply three existing search architecture to build a system that can manage all the information on Internet is an urgent problem. We just proposed such a system, Domain resource integrated system (DRIS), and are building the testbed in CERNET (China Education and Research Network).

What is DRIS?
1 Architecture DRIS is hierarchical information manage system, whose architecture is as same as that of DNS. Domain (defined in DNS) is the basic cell of DRIS. In every domain, a central server is built to manage information under this domain (4). The architecture of DRIS is shown in Fig.5.The node in the third layer corresponds to a third level domain like a university, and the second layer may be the sub network of one country like domain of "edu.cn". The node in top layer normally is a country. Every node of DRIS is an integrated search engine, but has different search scopes. Figure 5 the architecture of DRIS is as same as that of DNS. DRIS is a hierarchical distributed information retrieval system. Every node of DRIS will provide standard search service.
The size and diversity of data source Orgnization level 2 function structure DRIS appropriately adopts three kinds of search system in three layers.
In the third layer, centralized database system is applied to build search system. Node in this layer is always limited in a university or a company, and the size of its data source is very small. For example, the number of web pages in a university normally isn't more than one million, and most of current database systems can easily manage this kind of data source.
In the second layer, we adopt the metadata harvest system to build the information retrieval system. As a web search engine of node "edu.cn", we will integrate the all the web pages in all universities in China. Merely harvesting the metadata from thousands of DRIS servers in the third layer will be more efficient than directly downloading all the web pages from millions of web servers. The other kinds of resources can also be integrated by this means.
In the first layer, Distributed information retrieval system is applied to integrate the information resource in the scope of a country. In this layer, only the collection description data of resources is stored in database of DRIS. All the resources will cooperate to finish a user's query under the directing of DRIS. The function structure of DRIS is shown in Fig.6. Figure 6 DRIS suitably applies three kinds of information retrieval system to build the infrastructure of information retrieval for Internet. Organization lever-centralized system. Sub Internet level -metadata system. Country level-distributed system. DRIS can be treated as the management system of the biggest database in this world-Internet.
The size of data source markedly increases from the third layer to first layer. In appropriate scope (three levels domain), applying appropriate information retrieval architecture, and building appropriate information management frame for the whole Internet is the basic principle of DRIS.
The differences between DRIS and Google are detailed as follows. Third layer: centralized system (organization level ) may have to download the pages from a distance server. DRIS is managed by its users, just like management method of DNS. Every organization is its customer and also its builder. Decentralized management is much more effective than centralized administration in a large scale system. As the infrastructure of Internet, DRIS can almost cover all the information resources on Internet in theory. At the same time, its update interval can be only one day. 2 Opening and private. Search engines belong to corresponding companies, so they have to obtain profit from advertisement and ranking to maintain their subsistence. But DRIS is opening system, which needn't any profits from its users and of course need not any advertisements. Furthermore, In DRIS, every node will provide the standard search interface for anyone. So many intelligent personal search systems can use DRIS as their data source and provide high quality of search service. On the contrary, most search engines can only provide the same results for the same query words submitted by anyone. 5 The secret of DRIS DRIS will enormously improve the performance of Internet search engine in recency, coverage and so on, but this can't ensure the establishment of DRIS. The secret of DRIS will lies that it can balance the benefit and obligation between different organizations. Just in our testbed, education network, only few universities have the web search engine for the school network. Every university has also many characteristic information resources such as Ftp, BBS and special databases in library, but almost no a university have union search system that can efficient integrate all these resources, say nothing of sharing these resources with each other. These all bring the request for creating the underlying structure of DRIS. Solving some urgent problems of his own and then benefiting others may be the real guarantee of the success of DRIS. Moreover, the implementations of IPV6 will great prompt the information explosion, and also bring the requests for building an infrastructure of information management.


s2fieldsofstudy:
Computer Science
Physics

text:
A data Grid testbed environment in Gigabit WAN with HPSS

For data analysis of large-scale experiments such as LHC Atlas and other Japanese high energy and nuclear physics projects, we have constructed a Grid test bed at ICEPP and KEK. These institutes are connected to national scientific gigabit network backbone called SuperSINET. In our test bed, we have installed NorduGrid middleware based on Globus, and connected 120TB HPSS at KEK as a large scale data store. Atlas simulation data at ICEPP has been transferred and accessed using SuperSINET. We have tested various performances and characteristics of HPSS through this high speed WAN. The measurement includes comparison between computing and storage resources are tightly coupled with low latency LAN and long distant WAN.

Introduction
For the Atlas Japan collaboration, International Center for Elementary Particle Physics, University of Tokyo(ICEPP) will build a "Tier-1" regional center and High Energy Accelerator Research Organization(KEK) will build a "Tier-2" regional center for the Atlas experiment of the Large Hadron Collider (LHC) project at CERN. The two institutes are connected by the SuperSINET which is an ultrahigh-speed network for Japanese academic researches. On the network a Grid test bed was constructed to study requisite functionality and performance issues for the tiered regional centers.
High Performance Storage System (HPSS) with high density digital tape libraries could be a key component to handle petabytes of data produced by Atlas experiment and to share such data among the regional collaborators. HPSS parallel and concurrency data transfer mechanisms, which support disk, tape and tape libraries, are effective and scalable to support huge data storage. This paper describes about integration of HPSS into a Grid architecture and the performance measurement of HPSS in use over a highspeed WAN.

Test bed system
The computer resources for the test bed were installed in ICEPP and KEK site. One Grid server in each site and HPSS servers in KEK were connected with 1-Gbps Ethernet through the SuperSINET. All resources including network were isolated from other users and dedicated for the test. Figure 1 and Table I shows our hardware setup.
Three storage system components were employed. A disk storage server shared its host with the Grid server each at KEK and ICEPP. The remaining HPSS software components were used in the KEK Central Computer system. The HPSS data flow is depicted in Fig. 2. The HPSS Servers including core servers, disk movers, and tape movers are tightly coupled by an IBM SP2 cluster network switch.
In the case of original pftp(parallel ftp with Kerberos authentication) server performance measurement, pftpd was run in the core HPSS server. In the case of GSI-enabled HPSS server which will be mentioned in the section 4, pftpd was run in the same processors with the disk mover. The disk movers were directly connected to the test bed LAN through their network interface cards. Two HPSS disk movers were dedicated to the test.
NorduGrid middleware ran on the Grid servers. Other computing elements (CE) acted as a Portable Batch System (PBS) [1] that was not required to install with the NorduGrid middleware.
The NorduGrid [5] is a pioneer Grid project in Scandinavia that added upper layer functionality, which is necessary to HEP computing, on the Globus tool kit. The middleware was simple to understand and offered functionality sufficient for our test bed study. Table II shows the versions of middleware used in the test bed.

Basic network performance
Before end-to-end measurement, basic Gigabit Ethernet performance between IBM HPSS servers and a THCT002  host at ICEPP through the WAN as well as a host on the KEK LAN was measured using netperf [2]. It is shown in Figure 3 as a function of the TCP buffer size of the client. Round Trip Time (RTT) averaged was 3 to 4 ms. The network quality of service was quite good and almost free from packet loss (< 0.1%).
In this measurement, maximum TCP window size in HPSS server had 256kB (the buffer size of 256kB optimized to IBM SP2 switching network). The clients at both KEK and ICEPP had 64MB. Due to rather slower clock-speed proceessors on the HPSS servers the maximum raw TCP transfer performance was limited below 1Gbps. As seen in the graph, network access performance through both LAN and WAN became almost equivalent and saturated beyond 0.5MB buffer size. Figure 4 shows the network performance with the number of simultaneous transfer sessions through the WAN. In the situation where TCP buffer size was 100KB, up to 4 parallel simultaneous stream sessions improved network throughput. Using greater buffer size than 1MB, multiple stream sessions did not im-   Figure 5 shows data transfer speed by using the HPSS client API and comparison between access from LAN and over WAN. The transfer was from/to the disk of HPSS disk-mover disk to/from client host memory. The transferred file size was 2GB in all case. Disk access speed in the disk mover was 80MB/s. It shows that even with a larger API buffer size in the client API, WAN access speed was about a half of LAN access both for reading and writing from/to HPSS server.

HPSS client API performance
To increase HPSS WAN performance in future tests, the newer pdata protocol provided in HPSS 4.3 can be employed. This will improve pget performance. To get the same effect on pputs, the pdata-push protocol provided in HPSS 5.1 is required.
The existing mover and pdata protocols are driven by the HPSS mover with the mover requesting each data packet by sending a pdata header to the client mover. The client mover then sends the data. This exchange creates latency on a WAN. The pdata-push protocol allows the client mover to determine the HPSS movers that will be the target of all data packets when the data transfer is set up. This protocol eliminates the pdata header interchange and allows the client to just flush data buffers to the appropriate mover. The result is that the data is streamed to the HPSS mover by TCP at whatever rates it can be delivered by the client side mover and written to the HPSS mover devices.  Figure 5: HPSS client API performance 3.3. pftp client -pftpd server transfer speed Figure 6 shows data transfer speed by using HPSS pftp from HPSS disk mover to client /dev/null dummy device. Again as in the previous HPSS client API transfer, even with a pftp buffer size of 64MB, access speed from WAN was about a half of LAN access. In addition, enabling single file transfer with multiple TCP stream by using the pftp 'pwidth' option was not effective in our situation. In our server layout, two disk mover hosts each had two RAID disks. Therefore, up to 4 concurrent file transfers could effect higher network utilization and overall throughput, and was so seen in WAN and LAN access case. In the same figure (Fig. 6) data transfer speed was shown from HPSS disk mover to the client disks which had writing performance of 35-45MB/s. Though disks both in server and client hosts had the access speed exceeding 30MB/s and also network transfer speed exceeded 80MB/s, overall transfer speed dropped to 20MB/s. It is because these three resources were not accessed in parallel but in series. Figure 7 shows elapsed time for accessing data in tape library. Thanks to HPSS functionality and an adequate number of tape movers and tape drives, the data I/O throughput scaled with the number of concurrent file transfers. However, since the library had only two accessors and could load upto two tape cassetes to drives simultaneously, in the case where data in more than three off-drive tapes is required to access, the throughput goes down.
Comparison of writing to HPSS disk mover from client over WAN and LAN is shown in Fig. 8. In the figure, 'N files → N files', for example, means that 'reading' N files simultaneously at client and 'writing' N files to the server. In our setup, HPSS server had 4 independent disks but client had only one. Reading multiple files in parallel from a single disk at client side degrades the aggregate performance by contention of disk heads. pftp → pftpd; Client disk → Mover disk Figure 8: pftpd-pftp write to server cache-disk performance

GSI-enabled pftp
GridFTP[3] is a standard protocol for building data GRID and supports the featues of Grid Security Infrastructure (GSI), multiple data channels for parallel transfers, partial file transfers, third-party transfer and reusable and authenticated data channels.
The pftp and ftp provided with HPSS software was not required or designed to support data Grid infrastructure. For future releases, HPSS Collaboration Members have introduced data Grid pftp requirements and the HPSS Technical Committee (TC) has convened a Grid Working Group to propose a development plan. As an interim and partial HPSS data Grid interface solution, the HPSS Collaboration is distributing the GSI-enabled pftp developed by Lawrence Berkeley National Laboratory (LBL). The HPSS TC is also working with the GridFTP development project underway at Argonne National Laboratory.
To acquire an HPSS data Grid interface necessary for our test bed, we requested and received a copy of latest version of GSI-enabled pftp. The protocol itself is pftp but it supports GSI-enabled AUTH and ADAT ftp-command. Table III shows commands in each FTP protocol. While GSI-enabled pftp and GridFTP have different command set for parallel transfer, buffer management and Data Channel Authentication (DCA), the base command set is common. Fortunately unique functions of each protocol are optional and the two protocols are able to communicate. Installing and testing the GSI-enabled pftp, we proved that the GSIenabled pftp daemon from LBL could be successfully accessed from gsincftp and globus-url-copy with no dcau option(standard globus client utilities). From NorduGrid, the server was accessible as well. The below is a sample XRSL(Extended Resource Specification Language) which utilize GSI-enabled pftp server as a storage element(SE) of the NorduGrid.
in" "gsi\protect\vrule width0pt\protect\href{ftp://dt05s.cc:28 (stdout=datafiles.out) (join=true) (maxcputime="36000") (middleware="nordugrid") (jobname="HPSS access test") (stdlog="grid_debug")% (ftpThreads=1) In the performance measurement with 2GB file being accessed from 'pftp client', GSI-enabled pftp server and normal kerberos pftp server had equivalent elapsed data transfer time in any situation. Accessing from 'Grid-FTP client', GSI-enabled pftp server and normal pftp server, as well, had equivalent transfer time in usual. However, in the case where multiple disk movers were utilized and accessed data and GSI enabled-pftpd server resided in separated disk movers, transfer speed was halved. Figure 9 shows aggregate transfer speed over the number of independent simultaneous file transfer and shows the situation. After investigating the detailed communication between client and server, we found the differnece behaviour of the two servers. In original pftp where pftpd running in HPSS core server, data path is directly established between pftp client and disk mover. On the other hand, GSI-enabled pftp, data flow was from disk mover, via pftpd to client host. When the disk mover and pftpd server do not reside in the same host, two successive network transfer are incurred. # of file transfer in parallel Aggregate Transfer speed (MB/s) disk mver (!=pftpd) → client pftpd→pftp disk mver (=pftpd) → client GSI-pftpd→globus-url-copy disk mver (!=pftpd)→ client GSI-pftpd→globus-url-copy Figure 9: Read performance from GSI-enabled pftpd server to Gridftp client

summary
ICEPP and KEK configured NorduGrid test bed with HPSS storage server over high speed GbE WAN.
Data access performance was measured with several system configurations in comparison between LAN and WAN access. From that, we found that network latency affected data transfer speed with HPSS pftp and client API. The "GSI-enabled pftpd" developed by LBL was successfully adapted to the interface between Grid infrastructure and HPSS.
Our paper is a report on work-in-progress. Final results require that the questions relative to raw TCP performance, server/client protocol traffic, and pftp a protocol be further evaluated; that any necessary modifications or parametric changes be acquired form our HPSS team members; and that measurements be taken again. Further understanding of the scalability and the limitation of multi-disk mover configurations would be gained by measuring HPSS network utilization and performance using higher performance network interfaces adapters, system software and infrastructure, and processor configurations.


Indexing methods for efficient parsing

This paper presents recent developments of an indexing technique aimed at improving parsing times. Although several methods exist today that serve this purpose, most of them rely on statistical data collected during lengthy training phases. Our goal is to obtain a reliable method that exhibits an optimal efficiency/cost ratio, without lengthy training processes. We focus here on static analysis of the grammar, a method that has unworthily received less attention in the last few years in computational linguistics. The paper is organized as follows: first, the parsing and indexing problem are introduced, followed by a description of the general indexing strategy for chart parsing; second, a detailed overview and performance analysis of the indexing technique used for typed-feature structure grammars is presented; finally, conclusions and future work are outlined.

Introduction
One of the major obstacles in developing efficient parsers for natural language grammars is the slow parsing time. As recent years witnessed an increase in the use of unification-based grammars (UBG) or large-scale context-free grammars, the need for improving the recognition (parsing) times is more stringent.
Our approach is based on the observation that CFG or UBG parsing has to deal with large amount of data and/or data with complex structure, which leads to slower processing times. This problem is similar to that of the retrieval/updating process in databases, and for this area, it was solved by indexing. This similarity leads to the assumption that the same solution could be applied to parsing.
For chart-parsing techniques, one of the most timeconsuming operations is the retrieval of categories from the chart. This is a look-up process: the retrieved category should match a daughter description from the grammar. For large-scale CFGs, one position in the chart could contain a large amount of categories; for UBGs, this amount is usually smaller, but the unification process itself is very costly. Thus, as mentioned in (Carpenter, 1995), an indexing method that reduces the number of unifications is much needed.

Our Goal
Most of the research aimed at improving parsing times uses statistical methods that require training. As mentioned in (Malouf et al., 2000), during grammar development, the time spent for the entire edit-test-debug cycle is important, therefore a method needing considerable time for gathering statistical data could burden the development process. Our goal is to find better indexing methods that are time-efficient for the entire grammar development cycle.
Current techniques (such as quick-check, (Malouf et al., 2000)) reduce the parsing times by means of filtering unnecessary unifications. Using an index presents the advantage of a more organized, yet flexible, approach. Indexing methods are widely used in databases (Elmasri and Navathe, 2000) and automated reasoning (Ramakrishnan et al., 2001).

Related Work
An empirical method that addresses the efficiency issue is quick-check (Malouf et al., 2000), a method that relies on statistical data collected through training. Other techniques are focused on implementational aspects (Wintner and Francez, 1999), or propose approaches similar to indexing for typed-feature structures (TFS) retrieval (Ninomiya et al., 2002). An automaton-based indexing for generation is proposed in (Penn and Popescu, 1997), while (Penn, 1999b) improves the efficiency by re-ordering of feature encoding. A method (similar to the one introduced in Section 7) that uses pre-compiled rule filters is presented in (Kiefer et al., 1999), although the authors did not focus on the indexing potential of the static analysis of mother-daughter relations, nor present the indexing in a large experimental context.

Preliminaries
The indexing method proposed here can be applied to any chart-based parser. We chose for illustration the EFD parser implemented in Prolog (an extensive presentation of EFD can be found in (Penn, 1999c)). EFD is a bottomup, right-to-left parser, that needs no active edges. It uses a chart to store the passive edges. Edges are added to the chart as the result of closing (completing) grammar rules. The chart contains n 1 entries (n is the number of words in the input sentence), each entry i holding edges that have their right margin at position i.

TFS Encoding
To ensure that unification is carried through internal Prolog unification, we encoded descriptions as Prolog terms for parsing TFSGs. From the existing methods that efficiently encode TFS into Prolog terms ((Mellish, 1988), (Gerdemann, 1995), (Penn, 1999a)), we used embedded Prolog lists to represent feature structures. As shown in (Penn, 1999a), if the feature graph is N-colourable, the least number of argument positions in a flat encoding is N. Types were encoded using the attributed variables from SICSTus (SICS, 2001).

Chart Parsing with Indexing
In order to close a rule, all the rules' daughters should be found in the chart as edges. Looking for a matching edge for a daughter is accomplished by attempting unifications with edges stored in the chart, resulting in many failed unifications.

General Indexing Strategy
The purpose of indexing is to reduce the amount of failed unifications when searching for an edge in the chart. This is accomplished by indexing the access to the chart. Each edge (edge's category or description) in the chart has an associated index key, that uniquely identifies sets of categories that can match with that edge's category. When closing a rule, the chart parsing algorithm looks up in the chart for edges matching a specific daughter. Instead of visiting all edges in the chart, the daughter's index key will select a restricted number of edges for traversal, thus reducing the number of unnecessary unification attempts.

Index Building
The passive edges added to the chart represent rules' mothers. Each time a rule is closed, its mother is added to the chart according to the indexing scheme. The indexing scheme selects the hash entries where the mother 1 is inserted. For each mother M , the indexing scheme is a list containing the index keys of daughters that are possible candidates to a successful unification with M . The indexing scheme is re-built only when the grammar changes, thus sparing important compiling time.
In our experiments, the index is represented as a hash 2 , where the hash function applied to a daughter is equivalent to the daughter's index key. Each entry in the chart has a hash associated with it. When passive edges are added to the chart, they are inserted into one or several hash entries. For an edge representing a mother M , the list of hash entries where it will be added is given by the indexing scheme for M .

Using the Index
Each category (daughter) is associated with a unique index key. During parsing, a specific daughter is searched for in the chart by visiting only the list of edges that have the appropriate key, thus reducing the time needed for traversing the chart. The index keys can be computed offline (when daughters are indexed by their position, see Section 7) or during parsing (as in Sections 4, 6).

Indexing Method
The first indexing method presented in this paper is aimed at improving the parsing times for CFGs. The index key for each daughter is daughter's category itself. In order to find the edges that match a specific daughter, the search take place only in the hash entry associated with that daughter's category. This increases to 100% the ratio of successful unifications (Table 1 illustrates the significance of this gain by presenting the successful unification rate for non-indexing parser).

Experiments for CFG indexing
Several experiments were carried to determine the actual run-times of the EFD and indexed EFD parsers for CFGs.
Nine CFGs with atomic categories were built from the Wall Street Journal (Penn Tree Bank release 2) annotated parse trees, by constructing a rule from each sub-tree of every parse tree, and removing the duplicates.
For all experiments we chose a test set of 5 sentences (with lengths of 15, 14, 15, 13, and 18 words) such that each grammar will parse successfully all sentences and each word has only one lexical use in all 5 parses. The number of rules varied from 124 to 3196. Figure 1 shows that even for a smaller number of rules, the indexed parser outperforms the non-indexed version. As the number of rules increases, the need for indexing becomes more stringent. Although unification costs are small for atomic CFGs, using an indexing method is well justified. The performance measurements for all CFG experiments (as well as for TFSG experiments presented later) were carried on a Sun Workstation with an UltraSparc v.9 processor at 440 MHz and with 1024 MB of memory. The parser was implemented in SICStus 3.8.6 for Solaris 8.

Typed-Feature Structure Indexing
Compared to CFG parsing, for TFSGs the amount of attempted unifications is much smaller (usually UBGs have fewer rules than CFGs), but the unification itself is very costly. Again, indexing could be the key to efficient parsing by reducing the number of unifications while retrieving categories from the chart.
The major difference between indexing for CFGs and for TFSGs lies in the nature of the categories used: CFGs are mostly associated with the use of atomic categories, while TFSGs employs complex-structure categories (typed-feature structures). This difference makes indexing more difficult for typed-feature structure parsers, since the extraction of an index key from each category is not a trivial process anymore. The following sections describe the solution chosen for indexing typed-feature structure parsers.

Statistical and Non-Statistical Indexing
In our quest for improving the parsing times for TFSGs, we took two different approaches to indexing. The first approach uses statistical measurements carried on a corpus of training sentences to determine the most appropriate indexing scheme. The second approach relies on a priori analysis of the grammar rules, and no training is required.

Experimental Resources
For both statistical and non-statistical indexing schemes, a simplified version of the MERGE grammar was used. MERGE is the adaptation for TRALE (Meurers and Penn, 2002) of the English Resource Grammar (CSLI, 2002). The simplified version has 13 rules with 2 daughters each and 4 unary rules, and 136 lexical entries. The type hierarchy contains 1157 types, with 144 features introduced. The features are encoded as Prolog terms (lists of length 13) according to their feature-graph colouring.
For performance measurements, we used a test set containing 40 sentences of lengths from 2 to 9 words 3 (5 sentences for each length). For training the statistical indexing scheme we use an additional corpus of 60 sentences.

Path Indexing
Our statistical approach to indexing has its roots in the automaton-based indexing from (Penn and Popescu, 1997), used in generation, but adapted to indexed edge retrieval. The solution we chose is similar to the quickcheck vector presented in (Malouf et al., 2000). When parsing sentences in the training corpus, the parser is modified in order to record, for each unification between two feature structures that failed, the feature path that caused the unification failure. The path causing most of the unification failures across all training corpus will be refered to as the indexing path. The type value at the end of the indexing path is used as an index key.

Index Building
The indexing scheme used for adding edges to the chart during parsing is a slightly modified version of the general scheme presented in Section 3.2. Each edge is associated with an index key. For our statistical indexing, we used the type at the end of an edge's indexing path as the index key for that edge.
is the unique most general type, and § is the type unification.

Using the Index
The retrieval of edges from the indexed chart is accomplished as described in Section 3.3. The index key for each daughter is the type value at the end of the indexing path. In case the indexed path is not specified for a given daughter, the type is used for the key. Hence, searching for a matching edge in the entry described by is identical to using a non-indexed chart parsing.

Path Indexing with Quick Check
The path indexing scheme presented above makes use of a single feature path that causes most of the failed unifications over a corpus of sentences. Since each of the paths causing unification failures represents relatively small percentages of the total failures (the first two paths account for only 18.6% and 17.2%, respectively), we decided to use the first two paths in a mixed approach: the type at the end of the first path was still used as an index key, while the traversal of edges in a hash entry was accompanied by a quick-check along the second path.

Performance
Four parsers were tested: the non-indexed EFD parser, the path-indexed parser (using one path), the non-indexed EFD parser using quick-check, and the combination of path indexing and quick-checking. The results are presented in Table 2 Although the number of unifications dropped almost to 18% for the combination of path indexing and quickcheck, the difference in parsing times is not as significant. This is due to the costs of maintaining the index: simple path indexing is constantly slower than quick-check. Path indexing combined with quick-check outperforms quickcheck for sentences longer than 7 words.

Non-Statistical Indexing for TFS
Statistical indexing and quick-check have a major disadvantage if they are used during grammar development cycles. If the grammar suffers important changes, or the sentences to be parsed are not similar to those from training, the training phase has to be re-run. Hence, an indexing scheme that does not need training is needed.
The indexing scheme presented in this section reduces the number of hash entries used, thus reducing the cost of manipulating the index. The index key for each daughter is represented by its position (rule number and daughter position in the rule), therefore the time spent in computing the index key during parsing is practically eliminated.

Index Building
The structure of the index is determined at compiletime (or can be constructed off-line and saved for further uses if parsing is done with the same grammar). The first step is to create the list containing the descriptions of all rules' mothers in the grammar. Then, for each mother description, a list L Mother¡ daughters that can match Mother¨is created, where each element of the list L represents the rule number R i and daughter position D j (inside rule R i ) of a category that can match with Mother.
For CFGs, the list L Mother¡ would contain only the daughters that are guaranteed to match with a specific Mother (thus creating a "perfect" index). For UBGs, it is not possible to determine the exact list of matches, since the content of a daughter can change during parsing. However, it is possible to rule out before parsing the daughters that are incompatible (with respect to unification) with a certain Mother, hence the list L Mother¡ has a length between that of a "perfect" indexing scheme and that of using no index at all. Indeed, for the 17 mothers in the MERGE grammar, the number of matching daughters statically determined before parsing ranges from 30 (the total number of daughters in the grammar) to 2. This compromise pays off by its simplicity, reflected in the time spent managing the index.
During run-time, each time an edge (representing a rule's mother) is added to the chart, its category Cat is inserted into the corresponding hash entries associated with the positions R i D j ¡ from the list L Cat¡ . The entry associated to the key R i D j ¡ will contain only categories that can possibly unify with the daughter at position R i D j ¡ in the grammar. Compared to the path indexing scheme (Section 6.1) where the number of entries could reach 1157 (total number of types), in this case the number is limited to 30 (total number of daughters).

Using the Index
Using a positional index key for each daughter presents the advantage of not needing an indexing (hash) function during parsing. When a rule is extended during parsing, each daughter is looked up in the chart for a matching edge. The position of the daughter R i D j ¡ acts as the index key, and matching edges are searched only in the list indicated by the key R i D j ¡ .

Using Statistical Measures to Improve Non-Statistical Indexing for TFS
Although the statistical and non-statistical indexing techniques can be merged in several ways into a single method, the cost of maintaining a complicated indexing scheme overshadows the benefits. An experiment that combined all indexing techniques presented in this paper produced parsing times almost four times longer than the slowest non-statistical indexing. However, as shown in the following paragraphs, the statistical information about paths causing unification failures can be used to improve the efficiency of indexing.

Encoding Re-ordering
The unification of feature structures is accomplished by means of Prolog term unifications, as described in Section 2.1. This means that the unification of features encoded on the first position in their lists will take place before the unification of features that are encoded at the end of the lists. During the training phase presented in Section 6, we observed that features causing most of the unification failures are not placed at the beginning of the list in their encodings. Therefore, we re-arranged the placement of encoded features according to their probability to cause unification failures.

Performance
Similar to the experiments carried for statistical indexing, the experimental resources presented in Section 5.2 were also used for the indexing method introduced in Section 7. Figure 2 and Figure 3 present the comparison between the original EFD parser and the same parser with indexing (results from statistical indexing experiments are also presented here in order to illustrate the differences between all methods). For sentences having more than 4 words, the indexed parser outperforms both the EFD parser and the best statistical indexing method. Figures 2 and 3 also present the parsing times for the new feature encoding described in Section 8.1.

Conclusions
In this paper, we presented an indexing method that uses a hash to index categories during chart parsing. This method works for both context-free grammars with atomic categories, and typed feature structure grammars. The index keys rely on compatibility relations between rules' mothers and daughters statically determined before parsing. Other techniques (like statistic-based quickcheck tests or feature re-ordering) can be combined in order to improve the parsing time. Overall, static analysis of grammar rules that index daughters by their position proved to be an efficient method that eliminates the training needed by statistical indexing techniques. Statistical data can improve this method especially by means of feature re-ordering.

Future Work
Future work will focus on improving the indexing techniques analyzed in this paper. Possible areas of investigation are substitution tree indexing (Graf, 1995) for nonstatistical methods, or restructuring decision trees (Utgoff et al., 1997), while trying to maintain index operation costs at a minimum. Performance profiling combined with software and database engineering techniques will be used to determine the optimum trade-off between indexing efficiency and implementation cost.
Since non-statistical indexing proved to be an efficient solution, our main focus will be on improving the static analysis. Type signature and appropriateness specification will be used to identify both the paths prone to cause unification failures and the paths that lead to successful unifications. Empirical techniques (such as unifying partial representations for TFS ordered by their probability of causing unification failures) will be used, along with a more efficient feature encoding that allows for earlier detection of unification failures.


extfieldsofstudy: Physics Biology Mathematics

text:
Mechanisms of recoverable prevalence and extinction of viruses on linearly growing scale-free networks

We investigate mechanisms of the typically observed recoverable prevalence in epidemic spreading. Assuming the time-independent connectivity correlations, we analyze the dynamics of spreading on linearly growing scale-free (SF) networks, and derive the extinction condition related to the rates of network growth, infection, and immunization of viruses. The behavior is consistent with the previous results for SF networks by a mean-field approximation without connectivity correlations. In particular, it is suggested that the growing must be stopped to prevent the spreading of infection. This insight helps to understand the spreading phenomena on communication or social networks.

In the world-wide communication and transportation, we are able to work on rapid consideration or decision for scientific, technological, social, and business trends, while we are also frighten by threat to dangerous viruses for computer systems and our body itself. The needs become larger for understanding the mechanism of epidemic spreading and for finding effective strategies of the prevention against huge damage in economy or life by computer viruses via e-mails [10] [21], human immunodeficiency virus (HIV) [12], severe acute respiratory syndrome (SARS) [13], and so on. For the purposes, the study of infection disease on network models is useful. In particular, we should remark that many real networks, whose node and link are corresponding to individual (computer or person) and the (communicational, pathological, or sexual) contact between them, have scale-free (SF) structures based on natural rules of network growth with new nodes and preferential attachment for linking as rich-get-richer phenomenon [2] [4], in which the degree distribution exhibits a power-law as P (k) ∼ k −γ , 2 < γ < 3, for the probability of k connections in address-books of e-mails [8] [9] or sexual partners [12].
It is very possible that there exist a common mechanism for epidemic spreading in realistic SF networks, and that the extremely heterogeneity consisted of many normal nodes with less connectivities and a few hubs with much connectivities is crucial for the superspreading [13] and the persistence of viruses in long-time [21]. Indeed, the important properties of SF networks are the robust and vulnerable connectivities against random and targeted attacks, respectively [1]. The property is applicable for the targeted immunization for hubs [7] [19] to prevent the spreading of infection. Thus, the universal and robust structure in growing complex networks attracts physicists, and surprising results have been recently obtained.
In striking contrast with the usual models for epidemic spreading [3], it has been shown [17] that a susceptibleinfected-susceptible (SIS) model on heterogeneous SF networks has no epidemic threshold at a large network size nearly infinity; infection can be proliferated, whatever small infection rate they have. This result is closely related to the bond percolation problem. The epidemic threshold in a susceptible-infected-recovered (SIR) model coincides with the threshold for the bond percolation problem on networks [15]. On the other hand, in a closed system of the conventional susceptible-hidden-infectedrecovered (SHIR) or SIR model, the number of infection is initially increased and saturated, finally converged to zero as the extinction. The pattern may be different in an open system, in fact, oscillations have been described by a deterministic Kermack-McKendrik model [20]. However a constant population (equal rates of the birth and the death) or territorial competition has been mainly discussed in the model, the growth of computer network or world-wide human contacts is obviously more rapid, and the communications of mailing or the transportations are not competitive. Even in a new report for modeling the SARS epidemic [13], the mechanism of widely rapid spreading is not clear enough, though further treatments for the heterogeneity in transmission through superspreaders has been pointed out and the effectiveness of quarantine has been discussed. The strategic quarantine in both the model and experiences in Hong Kon is potentially related to prevent the typically observed recoverable prevalence [10] [21] in an open system as growing with new individuals. Fig. 1 shows an example of typically observed pattern in the prevalence of computer viruses.
Thus, we consider a growing system on heterogeneous SF networks for e-mails or human contacts, and investigate the mechanisms of recoverable prevalence and extinction of infection. In the previous paper [9], we have derived the conditions of extinction for the spreading in deterministic SIR models on SF networks by a mean-field approximation without the connectivity correlations. Although the connectivity correlations are not found in all growing network models and real systems [18], they are at least quantitatively significant for the spreading on heterogeneous SF networks [5] [6] [11]. In this paper, we extend the previous results to correlated cases between the degree of connections, and discuss the mechanisms of recoverable prevalence and extinction on linearly growing SF networks.
Heterogeneous SIR model.−On heterogeneous SF networks, we consider a deterministic SIR model [14] with macroscopic equations for the number of states. The state transition is from susceptible, infected, to recovered or immune, whose numbers for each connectivity k are denoted by S k (t) > 0, I k (t) > 0, and R k (t) > 0, respectively. Microscopically, susceptible nodes stochastically become the infected by contacts with infected nodes, which are recovered by the detection or immunization.
Assuming that infection sources exist in an initial small network and that both network growth and the spread of viruses are simultaneously progressed, we introduce a linear kernel [11] × t means a linear growth of network size. Since the maximum degree increases as progressing the time and approaches to infinity, it has a nearly constant growth rate ∞ k=m a k ∼ ∞ m Ak −ν dk = Am 1−ν ν−1 for large t. As shown in [11], the introduction of linear kernel is not contradiction with the preferential (linear) attachment [2] [4].
We first consider a simple case with only the detection of viruses. The time evolutions of S k > 0 and I k > 0 for each class of the connectivity k are given by where b and δ 0 denote the infection and detection rates between 0 and 1, the shadow variable R k (t) is implic- represents the expectation of infection by contacts from degree classes {l} to the degree class k.
We assume the correlation between degrees n kl = n lk , n k def = l n kl , and N kl ∼ n kl × t which is defined by the number of nodes with degree k attached to a node with degree l at the time t. We can easily check dN k dt = a k and the solution N k (t) = N k (0) + a k × t ∼ a k × t because of the initial small size (almost all N k (0) = 0 except for a few small k). The network is keeping the power-law degree distribution P (k) ∼ k −ν in growing. Although the growing in our model is not exactly same in Krapivsky-Render's GN model [11], the growth rate a k is close to We consider a section of I l = I * l : const. for all l = k. Fig. 2 (a) shows the nullclines of , and the vector filed for Eqs. (1)(2). There exist an equilibrium point: l n kl l −ν . On the state space, the viruses are not extinct by only the detection in even I * l = 0 (l = k), unless the growing is stopped as a k = 0.
Effect of immunization.−Next, we study the effect of random and hub immunization. With the randomly immune rate 0 < δ r < 1, the time evolutions are given by where the shadow variable R k (t) is also defined by dR k (t) dt = δ 0 I k (t) + δ r (S k (t) + I k (t)). On the section by assuming ∃I * l > 0 for l = k, the nullclines are (5) When the right hand side of (5) is denoted by f (Θ k ), for This means the growth and infection rates should be larger than the immune and detection rates according to the connectivity correlation of degree k.
On the other hand, we assume I * l = 0 for l = k to discuss the extinction. The necessary condition of extinction is given by that the point (0, a k δr ) on the hyperbolic nullcline of dS k dt = 0 is below the line S k =Ŝ k def = (δ0+δr )n k kbn kk : const. of dI k dt = 0. From the condition we obtain for n k ∼ a k asymptotically. From δ r < 1, we further derive as a limitation of growth rate or a weak correlation for the extinction. In this extinction case, there exists a stable equilibrium point, otherwise a saddle and a stable equilibrium point as shown in Figs. 2 (c)(d). Note that δ r > 0 is important for the extinction. When no growing a k = 0 (as a closed system) is applied to the above results, the condition (6) for damping oscillation is not satisfied, while the extinction condition (8) is satisfied. In other words, it is suggested that a growing network causes the recoverable prevalence of infection. By replacing a k = Ak −ν with the Krapivsky-Render's n k [11] and using their n kk = (k−1)(5k+2) k 2 (k+1) 2 (2k+1)(2k−1) , k ≥ 2, we can check that n kk < 1+2δ0 4kb is satisfied for any 0 < b, δ 0 < 1. The reason why viruses tend to be extinct in their GN model by even random immunization is that the infected parts are disconnected by recovered nodes on the tree structure, while our model generally has other bypass links than the links of tree in the difference of the degree distributions a k t and their n k t for small k, therefore infection can be spreading.
Moreover, for the hub immunization [7], δ r is replaced by 0 < δ h k τ < k τ , τ > 0. Then, the necessary condition of extinction in (8) is relaxed to larger However this is under the assumption of I * l = 0. If the general case for a section I * l = 0 is similar to Fig. 2  (a), then viruses in the class of degree k are not extinct unless the growing is stopped as a k = 0, otherwise they approaches to the extinction as shown from Fig. 2 (b) to (d). In fact, at the point (. . . , I k , S k , . . . , I l , S l , . . .) = (. . . , 0, a k δr , . . . , 0, a l δr , . . .), the eigenvalues of Jacobian are negligibly weak. Another extinction route is given by b → 0, in which case the condition (8) is satisfied for any A and n kk . It is consistent with the result of no epidemic threshold [17].
These dynamics are qualitatively same to the previous results by a mean-field approximation without the connectivity correlations [9]. In summary, we have investigate mechanisms of recoverable prevalence and extinction of viruses in SIR models with the connectivity correlations on linearly growing SF networks, and derived the necessary condition of extinction related to the growth, infection, detection, and immune rates. The results suggest that we must stop the growing of network or close it by quarantine to prevent the spreading of infection. A more general case in linearly growing SF networks on no assumption of correlation N kl ∼ n kl × t is further study.


On The Cost Distribution of a Memory Bound Function

Memory Bound Functions have been proposed for fighting spam, resisting Sybil attacks and other purposes. A particular implementation of such functions has been proposed in which the average effort required to generate a proof of effort is set by parameters E and l to E * l. The distribution of effort required to generate an individual proof about this average is fairly broad. When particular uses of these functions are envisaged, the choice of E and l, and the system design surrounding the generation and verification of proofs of effort, need to take the breadth of the distribution into account. We show the distribution for this implementation, discuss the system design issues in the context of two proposed applications, and suggest an improved implementation.

Introduction
Following Abadi et al [1], Dwork et al [2] suggest imposing computational costs on the senders of e-mail by requiring the mail to be accompanied by a proof of effort generated using a class of Memory Bound Functions (MBF). Specifically, they propose a concrete implementation called Algorithm Mbound. The average computational effort, measured in cache misses, it requires to generate a proof of this kind is set by two parameters E and l. Generating a proof requires on average E · l cache misses, verifying it requires l cache misses.
The distribution of effort required to generate an individual proof about the average of E · l is fairly broad. When particular uses of MBF are envisaged, the choice of e and l, and the system design surrounding the generation and verification of proofs of effort, need to take the breadth of the distribution into account.
We show this distribution and examine the resulting design issues in the context of the use of MBF both to impede spammers, and to assist the LOCKSS 1 (Lots Of Copies Keep Stuff Safe) system in resisting attacks [3]. We then propose an MBF implementation that has a better generation cost distribution and other advantages.

Memory Bound Functions
In this section we introduce Memory Bound Functions, and describe their application in spam prevention and in the LOCKSS protocol.

Background
The goal of a Memory Bound Function is to cause the generator of a proof to incur C cache misses and thus RAM accesses. If each of these takes t seconds, the generator must have used C ·t seconds on a real computer. Algorithm MBound has two adjustable parameters, the cost of verifying an effort proof l and the ratio, E, between l and the cost of constructing the proof. We measure all costs in cache misses, so a proof costs E · l cache misses to construct and l cache misses to verify. It uses an incompressible fixed public data set T larger than any cache it is likely to meet. A proof generator who must expend effort E · l is given as challenge a nonce n (so that older effort proofs cannot be reused) and the values of E and l. In response, the generator must perform a series of pseudorandom walks in the table T . Each starting point is determined by an index s which starts at zero and is incremented for each walk, or trial. The walk computes a one-way value A based on n, s and the encountered elements of table T . The walk is dependent on n and s; it is constructed so that the number of encountered elements is l, and fetching each encountered element causes an L1 cache miss. Each walk, therefore, causes l cache misses.
The generator stops when the value A computed by the walk has 0 bits in its least significant e = log 2 E positions. It is thus expected the generator will try on average 2 e walks with different starting positions determined by successive values of s before finding an appropriate starting position i, costing C = E · l cache misses.
The i that yielded the appropriate A is the effort proof. The verifier need only perform the random walk on T starting with the n he chose and the i sent by the generator, costing V = l cache misses. If the resulting A has the proper 0-bits in its last e positions, the verifier accepts the effort.
There is some non-zero probability that the proof search will take longer than any given number of steps. Dwork et al acknowledge this indirectly when they say: "If i > 2 2e the [verifier] rejects the message (with overwhelming probability one of the first 2 2e trials should be successful)." [2] Indeed, but what of the poor proof generator who had, using their parameters, expended more than 2 42 cache misses (about 10 days) and still failed to find a proof? It isn't just the verifier who must reject extremely long proofs, but also the generator. In any practical implementation of Algorithm MBound, account needs to be taken of the fact that some proportion of the attempts to generate a proof will fail simply because they took too long.

Use of MBF in Spam Prevention
The idea of using MBF to prevent spam is for a receiver to refuse to accept mail that is not accompanied by "postage" in the form of a proof of effort based on the sender's alias, the receiver's alias and the body of the message. The average amount of effort would be set to prevent an individual machine, even the fastest available, sending more than a few thousand mails per day. The goal of the spam adversary would be to reduce the actual effort required to send spam below this average.

Use of MBF in LOCKSS
The LOCKSS system implements a peer-topeer network of persistent, muutally suspicious  web caches used to preserve access to e-journals. The LOCKSS protocol requires a peer A requesting a service from a peer B to obtain a nonce from B, then provide B with a proof of effort based on that nonce representing more effort than B will need to perform the requested service. B verifies this effort before performing the service and returning the result to A. In the LOCKSS protocol, the service peers provide each other is that of voting on the digest of blocks of content. The proofs of effort prevent a conspiracy of a minority of malign peers overwhelming these votes, or cheaply swamping the system in bogus polls. Figure 1 shows the behavior of Algorithm MBound using the authors' choice of e = 15. We show histograms of the percentage of proof generations whose search ended after a given number of trials, and of the percentage of the total cost of proof generation due to those proofs. Note the skewed distributions; the majority of proofs take less than expected but, because they are cheap, the majority of the cost is due to proofs taking longer than expected.

Distribution of Proof Generation Effort
From this data we see that: • Even though the average cost of a proof is 32768 trials, more than 63% of the proofs are found in less than 16384 trials. The median proof lies between 8192 and 16384 trials, • There is almost 0.1% probability of finding a proof in 32 trials or less.
• There is almost 12% probability of finding a proof in 4096 trials or less.
• 9% of the total cost represents proofs taking  • 40% of the total cost represents paths taking more than twice as long as expected.
This behavior is not an artifact of the particular value of e they choose. Figures 2,3,4 show the behavior for e = 6, 12, 18 respectively.

Design Issues
In this section we discuss the issue raised by this distribution of effort proof costs for both the spam prevention and LOCKSS protocol applications.

What Does The Proof Prove?
At first sight it might appear that after the fact, the verifier of a proof knows how much effort was used to find it. The proof i in Algorithm MBound is, after all, a count of the number of trials. Although the verifier finds that index i produces a path terminating with a value with e low-order zero bits, that does not prove that no path j < i produces such a path. The verifier It is important to observe that the proof shows only that the generator did something that, averaged over a large number of repetitions by a generator using exactly the procedure specified, required approximately 2 e · l path steps.
The actual number of steps for the proof in question is unknown; it is quite likely to be less than 2 (e−3) · l. The average number of steps can be strongly influenced by the point at which the generator abandons the search as taking too long, a parameter that the generator doesn't reveal to the verifier. This uncertainty about the relationship between the requested and actual effort is a problem for both cases.

Tails of the Distribution
The left tail of Figure 1 is a region in which the cost of proofs curve is below the number of proofs curve. If a generator could manipulate things to increase the probability of being in this region it could generate proofs more cheaply than the verifier expects. Similarly, the right tail is a region in which the cost of proofs curve is above the number of proofs curve. If a generator could manipulate things to decrease the probability of being in this region it could generate proofs more cheaply than the verifier expects.
Both tails of the cost distribution pose problems for the LOCKSS protocol: • The significant population of low-cost proofs provides an adversary with a good chance of finding a proof much faster than expected.
• The significant proportion of the cost repre-sented by the small proportion of very long proofs allows an adversary to roughly halve his cost with little impact on his strategy simply by terminating the search for a proof early and failing to vote.
The LOCKSS protocol uses random challenges which appear to prevent attacks analogous to "chosen plaintext" attacks on encryption systems. Unfortunately, the fault-tolerance of the protocol allows the adversary to selectively refuse to supply expensive proofs and thus bias the "plaintext" towards cheap proofs.
Analogous difficulties arise in the application of Algorithm MBound to spam prevention. At first sight this case is also immune from a "chosen plaintext" attack, since the proof must be based on the text of the e-mail, its source and destination address, and so on. Unfortunately: • Spammers already perturb the text of their messages with random garbage their victims will ignore but which helps evade signaturebased spam filters. They could choose a email text and try many possible starting indices in parallel. If none produced a cheap proof, they could perturb the e-mail text and try again.
• Similarly, no individual recipient of spam is important. By terminating the search for a proof early; the spammer loses a proportion of the intended recipients but reduces his cost much more.

Adjusting Costs
The LOCKSS protocol needs to vary the additional costs imposed via the MBF scheme over a wide range to match the economic requirements of the protocol to the cost of the underlying hashing.
The LOCKSS application requires considerable freedom in setting costs, whereas for best results Algorithm MBound requires the values of e and l not to be too small, and incrementing e increases the cost by a factor of two. With these restrictions, the choice of e and l can be a problem.
Even in the spam application, setting prices of 0 (from known senders) or 1 (from unknown senders) for all e-mail "postage" lacks flexibility. An ideal design would allow the recipient to accept less "postage" from senders it trusted more.

Timing Uncertainty
To limit the possibility an adversary could "time-shift" and use a single computer to generate many votes in a single poll, the LOCKSS protocol sets deadlines by which a generator must deliver a proof. To do so, it must adjust for the difference between fast and slow memory systems. Dwork et al report this is a factor of 5. In addition, when using Algorithm MBound it must also adjust for the possibility that the generator may find a proof in many fewer or many more steps than expected. This "slop" in the timing defeats the purpose of the deadlines.
This uncertainty is not a problem in the spam application; since the recipient only sees the fixed time taken to verify the proof.

Requirements for MBF
The LOCKSS protocol's requirements for a cost function were stated [3] as: "First, it must have an adjustable cost, since different amounts of additional effort are needed at different protocol steps. Second, it must produce effort measurable in the same units as the cost it adjusts (hashing in our case). Third, the cost of generating the effort must be greater than the cost of verifying it." To these we can now add: • The distribution of actual effort involved in generating proofs of effort about the predicted mean cost must be narrow.
• It must not be possible for an effort generator to significantly reduce the average cost of proof generation by failing long proofs selectively.
• The proof must be concise, not requiring much data to be transmitted.
• The effort must be continuously adjustable.
In fact, we would like our proof to prove that the generator performed exactly E · l steps.

An Alternative MBF
Consider a mechanism in which the generator is asked to produce not a single index i which results in a value with e low-order zeros, but a list of all i in a specified range which result in values with e − m low-order zeros, where 2 m is the expected number of such values. The verifier can cheaply verify some indices randomly chosen from the list, if any are invalid the proof is invalid. The more indices are verified, the more sure the verifier is of the effort expended by the generator. If the verifier considers extra verification effort justified, a search of some randomly chosen intervals between the indices in the list that revealed indices resulting in values with the required number of zeros would also render the proof invalid. The generator doesn't know which indices and ranges the verifier will check, so cannot include bogus entries without risking discovery.
In this way we force the generator to explore an entire range of indices, rather than stopping at the first one. The number of trials needed to generate a proof is fixed, because every index in the requested range must be checked if the generator is unwilling to risk the cheat being discovered. This satisfies the first two of our additional requirements.
There will be considerable variation in the cost of verifying a proof, depending on how sure the verifier wants to be that the generator actually exerted the requested effort.
This mechanism has some attractive features: • There is no uncertainty as to the amount of effort exerted by the generator; unless it is willing to risk detection it must perform exactly the effort requested.
• The verifier never performs more effort than the generator; it can stop as soon as any trial is invalid.
• The more effort the verifier performs, the better the verification. The amount of this effort can be adjusted to match the verifier's suspicion of the generator. This property is valuable in both applications we consider: -Spammers wish to conceal their true identity behind a screen of proxies, making it unlikely that a recipient would engage in repeated transations with the same apparent spammer identity. But a recipient normally has re-peated transactions with many legitimate e-mail senders; reducing the cost of verifying their identities would reduce the total cost of the system to a recipient.
-In the LOCKSS case, repeated transactions are the norm and this property would be very useful.
• It provides another parameter with which to adjust the cost of the proofs requested from a generator, namely the size of the range of indices to be searched. In the LOCKSS case, this helps adjust the effort requested to the economic requirements and the underlying hash cost.
• In effect, we have converted the uncertainty in time inherent to Algorithm MBound into uncertainty in size; there is a non-zero probability that every value in the requested range on indices has the required number of low-order zeros and must be included in the proof. There is no upper bound on the time required by Algorithm MBound, there is none on the message size required by our new scheme.
Note that in this scheme there may not be any indices i in the requested range which result in values with e − m low-order zeros. Thus an empty list of indices is potentially a valid proof of effort, albeit one that is anomalously expensive to verify. If an empty proof is valid, verifying it takes as much effort as generating it. If it is invalid, the first valid path found in the range shows this. On average this takes 1/2 m of the effort that should have been used to generate the proof. This poses a problem; an adversary can generate empty proofs free and cause verifiers to waste on average 2 (e−m) trials to reveal they are invalid: • In the spam case, the recipient should reject all empty proofs. A sender finding an empty proof should perturb the message and try again.
• In the LOCKSS case, the requestee should reject all empty proofs. If the parameters can be set to make empty proofs sufficiently rare, the fault tolerant nature of the protocol means that this will have little effect.

Setting Parameters
The authors chose parameters for Algorithm MBound that prove 2 15 paths each 2 12 steps long, and thus 2 27 cache misses. To choose comparable parameters for our scheme, we start by setting m = 4 to keep the average proof size to 16 indices or 64 bytes. If we use the same path step mechanism as Algorithm MBound, we also need to set l = 2048 and thus need a range of 2 e = 2 15 indices to search. We thus look for paths generating a value with (e − m) = 11 loworder zeros. With these choices, the probability that all 2 15 trials fail to find any such path is (1 − 1/2 4 ) 2 15 or about 10 −7 .

Future Work
We have yet to implement our new scheme in the LOCKSS protocol. We expect it to resolve many tricky issues that arose in our attempt to use Algorithm MBound. Doubtless, other tricky issues will arise as we proceed. It may well be that the path generation part of Algorithm MBound is not the best choice for generating the larger number of smaller sub-proofs that our scheme needs; this is the subject of further exploration.

Conclusion
We have shown that the actual cost, measured in the number of trials, needed to generate a proof of effort using Algorithm MBound has a fairly broad distribution. We have identified a number of design issues this raises for a practical application of this scheme to both its intended spam prevention purpose, and for adjusting the cost of operations in the LOCKSS protocol. We suggest an alternative scheme, in which the cost of generating a proof is fixed and the cost of verifying a proof can be adjusted by the verifier to match his suspicions of the generator.

Acknowledgements
This material is based upon work supported by the National Science Foundation under Grant No. 9907296, however any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation. static double totalCost = 0;


Flexible and personalizable mixed-initiative dialogue systems

This paper describes our vision for a future time when end users of mixed-initiative spoken dialogue systems will be able to dynamically configure the system to suit their personalized goals. We argue that spoken dialogue systems will only become a common utility in society once they can be reconfigured, essentially instantaneously, to support a new working vocabulary within a new domain or subdomain. For example, if a user is interested in restaurants in Seattle, the system would go off-line to gather information from resources such as the Web, and would infer from that knowledge an appropriate working vocabulary, language models, and dialogue control mechanism for a subsequent spoken conversation on this topic. In addition to painting this vision, the paper also discusses our recent research efforts directed towards the technology development necessary to realize this larger goal.

Introduction
Spoken dialogue systems are emerging as an effective means for humans to access information spaces through natural spoken interaction with computers. These systems are usually implemented with a static knowledge space, or one that is only augmented through manual intervention from the system developers. A significant enhancement to the usability of such systems would be the ability to automatically acquire new knowledge through interaction with its end users and its available knowledge resources. We believe, in fact, that the main barrier to wide acceptance of spoken dialogue systems is their current lack of flexibility and personalization.
Over the past decade, researchers in the Spoken Language Systems Group at MIT have been developing hu-man language technologies for mixed initiative conversational systems, which are distinguished from the emerging deployed commercial systems in that the interaction is natural and flexible, modelled after the style of humanhuman dialogue (Zue and Glass, 2000). The development of the Galaxy Communicator architecture (Seneff et al., 1998) has greatly accelerated the pace at which we as experts can configure complex dialogue systems in a wide range of different domains. As the underlying technology components have matured, our research focus has evolved to include issues related to portability, modularity, and dynamic configurability of system components. We believe that the ability for naive system developers, and even end users, to reconfigure existing systems to manage their personal needs, will be crucial for the successful use of these technologies.
We see several different ways in which such flexible reconfiguration will become feasible in the near future. Perhaps most critical is the initial preparation of a new domain, where available on-line databases will be the catalyst for defining the vocabulary and language models of the domain, as well as the nature of the dialogue interaction needed to guide the user through the information space (Polifroni et al., 2003). However, the ability to dynamically reconfigure based on new information will also be extremely valuable. For instance, a hotel domain for the entire U.S. might initially restrict name recognition to the major chains such as Sheraton and Hyatt, since it would not be feasible to support all hotel names in the U.S. Once the user defines a specific geographic region, the system can enhance the level of detail of its working vocabulary, but particular to the user's narrower request, now supporting explicit mention of perhaps all hotels by name within that designated region. Users would be able to select hotels based on a number of attributes as guided by the hotel database, and to specify constraints in general world knowledge areas such as dates and prices. Users should be able to further personalize the system There is one seafood restaurant on Hanover Street. The others are Italian. User: I'm interested in the Seafood restaurant. Sys: The Daily Catch is located on 323 Hanover Street. The phone number is 617-523-8567. The price range is between $12 and $18. by adding new words instantaneously to the working vocabulary via spoken dialogue. This might also include specifying the word's semantic class: "I want to add the name John Doe to my rolodex." When feasible, a userspecified named entity, such as a restaurant, would be verified against Web sources to improve the system's ability to understand their request.
In order for this vision to become a reality, a number of specific technology goals must be met. First and foremost, it is essential to develop tools that will enable rapid configuration of dialogue systems in new domains of knowledge, guided mainly from domain-dependent information sources. Our efforts in generic dialogue development represent a strong initiative toward that goal (Polifroni and Chung, 2002). Secondly, we need to be able to support incremental update of vocabularies and language models for speech recognition and understanding, in essentially instantaneous time (Schalkwyk et al., 2003;Seneff et al., 1998;. This would allow great flexibility within a single dialogue where the user might ask about a named entity that is not yet known to the system. Third, while we can make use of a large lexical resource for pronunciation modeling, we must have available as well a high-performance letter-to-sound capability, integrating multiple knowledge sources such as a Web page, a spoken name, a spoken spelling of the name, and/or a key-padded name (Chung and Seneff, 2002). Fourth, we need to have intelligent knowledge acquisition systems, capable of populating a database from Web sources, and extracting and organizing key elements from the database (Polifroni et al., 2003).
These ideas can best be illustrated through a couple of example scenarios. In Figure 1, the user begins with a request for a restaurant in a neighborhood of Boston. The system then rapidly configures itself to support the appropriate sub-language, and is able to summarize lists of restaurants meeting the constraints of the user's subsequent queries, eventually leading to a unique selection.
For the scenario in Figure 2, the user has asked about User: Can you tell me the phone number of the Thaiku restaurant in Seattle? Sys: I may not know the name of the restaurant. Can you spell it for me? User: t h a i k u Sys: The phone number of Thaiku is 206-706-7807. Figure 2: A sub-dialogue to enroll a new restaurant name.
the phone number for a restaurant they already know about. The system parses the name within a complete parse, but with a generic "unknown word" as a stand-in for the restaurant name. It can at this point go to the Web and download a set of candidate restaurant names for Seattle, to form additional constraints on a solicited spelling. The integration of the spelling, the spoken pronunciation, and the Web listing, we argue, potentially provide enough constraint to solve the specific problem with high accuracy. The system can now retrieve the requested information from the Web.

Underlying Technologies
Over the past several years, we have been making advances on several fronts, directed toward the larger goal of the vision outlined above. In this section, we will highlight some of these, with pointers to the literature for an in-depth description. SpeechBuilder: Over the past few years, we have been developing a set of utilities that would enable research results to be migrated directly into application development (Glass and Weinstein, 2001). Our goal is to enable natural, mixed-initiative interfaces similar to those now created manually by a relatively small group of expert developers. We make no distinction between the technology components of SpeechBuilder and those of our most sophisticated dialogue systems, such as the Mercury flight reservation domain (Seneff and Polifroni, 2000). Speech-Builder employs a Web-based interface where developers type in the specifics of their domain, guided by forms and pull-down menus. Components such as recognition vocabulary, parse rules, and semantic mappings are created automatically from example sentences entered by the developer. In several recent short courses, naive developers have been able to implement a new domain and converse with it on the telephone in a matter of hours. Language Modelling: Patchwork Grammars A serious limitation in today's technology to immediate deployment of a new system is the chicken-and-egg problem of the language model. System performance is critically tied to the quality of the statistical language model, which typically depends on large domain-dependent corpora that don't exist until the domain is actually deployed and widely used. We have initiated an effort to automatically induce a grammar for a new domain from related content of existing speech corpora for other domains combined with knowledge derived from the content provider for the new domain. For instance, our hotel domain can leverage from an existing auto classified domain to extract patterns for referring to prices, can induce a grammar for dates from a flight domain, and can make use of statistics of hotel counts to determine city probabilities. Parse rules for general sub-domains such as dates, times, and prices are organized into sub-grammars that are easily embedded into any application, along with libraries for converting the resulting meaning representations into a canonical format, such as "27SEP2003." Flexible Vocabulary: We have recently realized our goal of enabling users to automatically add a new word to an existing system through natural interaction with the system itself (Schalkwyk et al., 2003;Seneff et al., 1998;Chung and Seneff, 2002;. We have thus far applied this only to the enrollment of the user's name as part of a personalization phase (Seneff et al., 1998;, through a "speak and spell" mode. After confirmation, the system reconfigures itself to fully support the word such that it can now be understood in subsequent dialogue. A high quality sound-to-letter framework  and a new ability to automatically derive a class n-gram from an NL grammar have facilitated this process . The recognizer update is currently implemented via full recompilation, which can take up to a minute of elapsed time, but efforts to support incremental recognizer updates (Schalkwyk et al., 2003) hold promise for essentially instantaneous new word addition. Managing the Dialogue: One of the most time consuming aspect of dialogue system development today is the implementation of the dialogue manager. To reduce this development phase, we have been creating a set of domain-independent functions that can be specialized to a particular domain through passed parameters.
These functions perform such tasks as checking a query for completeness, filtering the database results on userspecified constraints, or making decisions on fuzzy attributes such as "near" (Polifroni and Chung, 2002). One common but important subgoal in dialogue planning is to generate a succinct description of a set of retrieved entries. Our recent research in this area has focused on organizing database retrievals into a summary meaning representation, by automatically clustering sets into natural groupings. In parallel, we are developing generation tools that will translate these summaries into fluent English. For instance, in the hotel domain, the result set is automatically partitioned into "cheap" or "expensive" differently depending upon the city. By basing such subjective categories on a content provider, we alleviate the burden of the system developer, while at the same time producing a more intelligent system.

Summary and Conclusions
While there is inadequate space here to properly cover such a large topic as flexible and rapidly reconfigurable mixed-initiative dialogue systems, we hope that we have managed to convey our long-term research goals adequately and to provide the excitement that we ourselves feel in our current efforts to turn this vision into a reality. In fact, important subgoals that we have had for many years, such as incremental vocabulary update, grammar development and training through recycled resources, and tools to enable rapid development of effective dialogue interaction, are now finally bearing fruit. We believe that this is a critical moment in the life of dialogue system research, and we anticipate exciting breakthroughs in the near future, leading to systems that are not only useful but also easy to use and accommodating, such that users will prefer them over alternative means of acquiring their information needs.


extfieldsofstudy:
Medicine
Materials Science
Physics
Biology

text:
Percolation, Morphogenesis, and Burgers Dynamics in Blood Vessels Formation

Experiments of in vitro formation of blood vessels show that cells randomly spread on a gel matrix autonomously organize to form a connected vascular network. We propose a simple model which reproduces many features of the biological system. We show that both the model and the real system exhibit a fractal behavior at small scales, due to the process of migration and dynamical aggregation, followed at large scale by a random percolation behavior due to the coalescence of aggregates. The results are in good agreement with the analysis performed on the experimental data.

The problem of morphogenesis and self-organization in biological systems is both an actual and a long standing one [1,2]. In living beings, complex structures arise from the aggregation of separate constituents. Such structures, although irregular, often show some sort of hidden order, like self-similarity and scaling laws [3,4]. Scaling laws are known to emerge not only in the physics of phase transition [5] and in percolation [6], but also from several kinds of aggregation dynamics, and are often considered as fingerprints of the process which led to the formation of the structure itself [7,8]. A typical example of natural structure characterized by non trivial scaling laws is the vascular network [9]. In recent years many experimental investigations have been performed on the mechanism of blood vessel formation [10]. Cells are cultured on a gel matrix and their migration and aggregation observed through videomicroscopy. Tracking of individual trajectories shows marked persistence in the direction, with a small random component superimposed [11]. The motion is directed towards zone of higher concentration of cells, suggesting that chemotactic factors play a role. Cells migrate over distances which are an order of magnitude larger than their radius and aggregate when they get in touch with one of their neighbors. In a time of the order of 10 hours they form a continuous multicellular network which can be described as a collection of nodes connected by chords. The mean chord length is approximately independent on the initial cell densityn, with an average valuel = 200 ± 20 µm for n between 100 to 200 cells/mm 2 . Observing the formed structures, one finds that, by varying the initial cell density, there is a percolative transition. Below a critical value n c ∼ 100 cells/mm 2 groups of disconnected structures are formed (Fig. 1a). Forn ≥ n c a single connected network is instead visible (Fig. 1b,c). For higher values ofn one observes a sort of "swiss cheese" pattern ( Fig.  1d). In the biological system the percolating property is of physiological relevance, since it is directly linked with the functionality of blood vessels.
In this paper we propose a theoretical model which turns to be in good agreement with experimental observations. It allows to well reproduce both the observed percolative transition and the typical scale of observed vascular networks. With respect to standard percolative models, here an important role is played by migration and dynamical aggregation of particles. The model appears thus as a possibly new and physically interesting representative in the class of percolation models. We characterize the phase transition from the point of view of scaling laws, both in the model and in the real system, computing critical indices and the fractal dimension of the percolating cluster through extensive numerical simulations and analysis of the experimental data. The model describes the cell population as a continuous density field n and velocity v; it also assumes the presence of a concentration field c of soluble factor. Cells are modeled as a fluid accelerated by gradients of the soluble factor. The latter is supposed to be released by cells, diffuse, and degrade in finite time, in agreement with experimental observations. These assumptions give rise to the following equations: where D, α, τ , are respectively the diffusion coefficient, the rate of release and the characteristic degradation time of soluble mediators, and µ measures the strength of cell response. Initial conditions are given in the form of a set of randomly distributed bell-shaped bumps in the density field, representing single cells initially spread in the system, with zero velocities and zero concentration of the soluble factor. In Eqs. (1) a multidimensional Riemann (1b) equation is coupled to the diffusion equation (1c), while (1a) is just a continuity equation expressing conservation of the total cell number. Multivaluedness of solutions to (1b) can be prevented by adding a viscous term ∇ 2 v in the r.h.s. One than gets the analog of Burgers' equation, which has been used to describe growth of molecular interfaces [12] and the emergence of network-like patterns [13] in the large-scale distribution of masses of the Universe [14,15]. Instead of viscosity, we introduce a phenomenological, density dependent pressure term −∇φ(n), in the r.h.s. of (1b), with φ(n) zero for low densities, and rapidly increasing for densities above a threshold σ −2 , where σ = 30 µm is the mean cell radius, in order to describe the fact that cells do not interpenetrate.
The model provides a natural lenght scale r 0 = √ Dτ , which is the effective range of the interaction mediated by the soluble factor. This suggests that, starting from the above mentioned initial conditions, Eqs. (1) should develop network patterns characterized by the same scale. Direct measurements of D and τ give D ∼ 10 −7 cm 2 /s, τ ∼ 1h, from which one gets r 0 ≃ 200 µm, a value which is in good agreement with the mean chord lengthl experimentally observed.
We performed numerical simulations of model (1) on square boxes of size L = 1, 2, 4, 8 mm, with periodic boundary conditions, using a finite volume method [16]. We used the experimental values for D and τ , while the unknown parameters µ, α were set to one (which amounts to an appropriate rescaling of time and the concentration field c). The initial conditions were given by throwing the same number of cells as in the biological experiments in random positions inside the box, with zero velocities and zero concentration of the soluble factor, with a single cell given initially by a Gaussian bump of width σ and unitary weight in the integrated cell density field n. Starting from these condition, Eqs. (1) were numerically integrated. The simulation was stopped when the vascular network was formed, or a stationary state was reached. We observed a remarkable correspondence between simulations and experiments both in the the dynamic evolution details (not shown) and in the reproduction of the percolating patterns (Fig. 2).
In order to study the percolative transition we computed between 100 to 200 realizations of the system for each box size and cell density, with different initial positions of the cells. The simulation gives as a result a continuous density field n. In order to study percolation properties we partitioned the box in little square boxes of size 2 −6 mm, forming the sites of a square lattice, and set each site as filled if the mean cell density inside the corresponding little box was larger than the threshold σ −2 , empty otherwise. We then identified clusters of nearest neighbor filled sites. In Fig. 2  represent the underlying substrate. As in the case of experimental data, a percolative transition is observed at some critical cell density n c . Furthermore the model reproduces quite well the typical structure of the vascular network, with chords of lengthl ≃ 200 µm for a wide range of cell densities, in good agreement with the expected value r 0 . For each set of realizations, corresponding to a value of the box size L and of the mean cell densityn, we identified clusters of nearest neighbor filled sites, and measured the following quantities: 1) the percolation probability Π, defined as the fraction of realizations in which a percolating cluster appears; 2) the infinite cluster density P , defined as the density of sites belonging to the infinite (greatest) cluster; 3) the mean cluster size S = (1/N ) s n s s 2 , where N is the total number of sites and n s is the number of clusters of size s, excluding from the sum the infinite cluster. In percolation models, in presence of a second order transition at some mean cell density n c , these quantities show a characteristic singular behavior near the percolation point. Namely, the percolation probability is zero below the transition and one above it; the infinite cluster density, which plays the role of order parameter, vanishes as |n − n c | β from above; and the mean cluster size has a singularity |n − n c | −γ on both sides of the transition. For finite size systems, the same quantities obey near the transition to the following relations: Using Eq. (2a), one can find the critical density n c as the point where the curves Π(n, L) for different sizes L cross. The estimated value is n c = 94 ± 1 cells/mm 2 . Then, the critical index ν is found by plotting Π(n, L) as a function of (n − n c )L 1/ν , where n c is held fixed to the value previously computed, and looking for the value of ν that gives the best data collapse. The error on the computed value of the index is estimated looking for the range of values that gives an acceptable data collapse.
Holding the value of n c and of ν fixed, the other two relations Eq. (2b) and (2c) are used to estimate the value of the indices β and γ, by looking for the data collapse of L β/ν P (n, L) and L −γ/ν S(n, L) as a function of (n − n c )L 1/ν . We observed that while n c is sensitive to the choice of the threshold in a neighborhood of the natural value σ −2 , the critical exponents do not depend on it. In Fig. 3 the data collapses for Π and S are shown. The estimated values of the critical indices are reported in the second column of Tab. I. Within the errors, the values obtained are the same that one expects for the simple random percolation model, that is when the sites of the lattice are uncorrelated, and each one occupied with the same probability. As critical indices are linked to the large scale structure of the percolating cluster, this means that, on such a large scale, the structure of the vascular network is mainly determined by the initial random positioning of the cells,  and is not altered by the dynamical process of migration and aggregation. On the other hand, on smaller distances clusters are quite different from the ones of random percolation. For example the mean fraction of occupied sites, which is a quantity sensible to the small scale structure of clusters, is about 0.2 at the percolation point, much lower than the corresponding figure for random percolation, that is 0.59. A quantity that can give us informations about the structure of the percolating cluster at different scales is the density ρ(r) as a function of the radius. This is defined as the mean density of sites belonging to the percolating cluster, inclosed in a circle of radius r centered at one site belonging to the cluster, and averaged over different centering sites and different realizations of the system. For a fractal object with fractal dimension D, this should scale as ρ(r) ∼ r D−d . For the percolating cluster of random percolation at the critical point, one expects a fractal dimension D = 1.896. We computed ρ(r) for our model at the percolation point n = n c (see Fig. 4), and found two different regimes depending on the scale. For r > r c , with r c = 0.77 ± 0.08 mm, a behavior compatible with random percolation is found, with fractal dimension D = 1.87 ± 0.03. On the other hand, for r < r c a different exponent is found, D = 1.50 ± 0.02. This exponent may be the signature of the dynamic growth process driven for r < r c by the rapidly oscillating components of the concentration field. We have repeated the measures described above on a set of experimental data, consisting of 28 digital photographs (with a resolution of 1024 2 pixels) of mature structures obtained on a matrix of size L = 2 mm, starting from initial densities of 50, 75, 100, . . ., 200 cells/mm 2 . The photographs are the results of two experimental sessions, each performed in duplicate, so that 4 photographs are available for each density value. The data show the presence of a percolative transition at n c ∼ 125 cells/mm 2 , and are compatible with the values γ/ν = 1.83 obtained from numerical simulations. The available data are not enough to obtain ν and β/ν with a reasonable precision. Estimated values of the critical indices are reported in the third column of Tab. I. Finally, we measured the density of the percolating cluster as a function of the radius at the percolation point, and found a behavior surprisingly similar to the one found in the numerical model (see Fig. 4): for r > r c the fractal dimension of the percolating cluster is D = 1.85 ± 0.10 which is compatible with D = 1.87±0.03 from the numerical simulations and with the value D = 1.896 of random percolation. For r < r c instead D = 1.48 ± 0.05.
In conclusion, we have introduced a model which describes the formation of the vascular network with a typical scale lenght r 0 , and is in good agreement with experimental data. The percolative phase transition appears to be second order, at least to the accuracy allowed by the limitations in size which are intrinsic to our numerical experiments. Comparison of critical indices suggests that the phase transition falls in the universality class of random percolation, even in presence of migration and dynamical aggregation. This is confirmed by the fractal dimension of the percolating cluster, on scales larger than r c ≃ 0.8 mm, that is in agreement with the one expected for random percolation. On the other hand we found that, if observed on scales smaller than r c , the vascular network shows a different scaling behavior, with a fractal dimension D ≃ 1.5, that may be the signature of the dynamical process that led to the formation of the network. Thus, the model appears to be quite successful in describing in vitro experiments, where all the parameters are under control and one can easily tune the cell density. It would also be interesting to understand the relevance of this picture to vascular networks in living beings. It is known [10] that during embriogenesis blood vessels form through local (in situ) differentiation of a fraction of endothelial cells, that afterwards assemble in a vascular labyrinth, a process similar to the one described in this paper. However, in this case it is more difficult to have complete control over all the relevant parameters.
In particular, one would expect that the cell density is fixed through some feedback mechanism, in order to maximize efficiency [9]. Indeed, some experiments [17] on in vivo capillaries show compact space-filling structures, with fractal dimension D = 2, which would indicate that cell density is tuned by Nature to a value larger than the percolation threshold. More experiments, focusing on the relevance of the percolation mechanism, and the nature of cell density self-regulation, are needed to shed light on these issues.