Internet-Based Intervention for

Imagery Rehearsal Therapy (IRT), a cognitive therapy consisting in positively transforming nightmares into dreams with a more positive content, developed by Barry Krakow [START_REF] Krakow | Imagery rehearsal treatment for chronic nightmares[END_REF], is the most effective treatment for chronic nightmares [START_REF] Morgenthaler | Position Paper for the Treatment of Nightmare Disorder in Adults: An American Academy of Sleep Medicine Position Paper[END_REF]. Recently, Gieselmann et al. [START_REF] Gieselmann | The Effects of an Internet-Based Imagery Rehearsal Intervention: A Randomized Controlled Trial[END_REF] validated the feasibility of using telemedicine-delivered IRT for idiopathic nightmares. Their sound methodology demonstrates how internet-based intervention, with minimal guidance from a coach, can be effective. However, their "results cannot be generalized to posttraumatic nightmares due to the strict selection criteria enforced by ethical obligations." Nightmares affect the majority of patients suffering from Posttraumatic Stress Disorder (PTSD) and occur twice as frequently in PTSD than in any other psychiatric disorders [START_REF] Swart | Prevalence of nightmare disorder in psychiatric outpatients[END_REF]. While telepsychology is known to offer moderate to large improvements in the treatment of PTSD [START_REF] Bolton | Telepsychology for Posttraumatic Stress Disorder: A systematic review[END_REF], no study on remote IRT for the treatment of traumatic nightmares has yet been published. The main objective of the current study was to generalize the results of previous remote IRT studies [START_REF] Gieselmann | The Effects of an Internet-Based Imagery Rehearsal Intervention: A Randomized Controlled Trial[END_REF][START_REF] Lancee | Cognitive-behavioral self-help treatment for nightmares: a randomized controlled trial[END_REF] to traumatic nightmares including those experienced in PTSD. This study implemented a prepost design comprising baseline, post-treatment (3 months after treatment), and follow-up measurements (6 months after treatment). A videoconference interview was conducted for diagnosis (Mini-International Neuropsychiatric Interview according to DSM-IV-TR). Exclusion criteria were: exposure to a traumatic event over a period of less than 3 months, following treatment for PTSD, psychosis, night terrors, sleepwalking, sleep paralysis, narcolepsy, sleep-disordered breathing, neurological disorders, or significant modification of consumption of substances influencing dreams during the study (hypnotics, beta-blockers, neuroleptic drugs, antidepressants, and alcohol).

The remotely administered treatment complied with recommended formatting for practicing IRT [START_REF] Krakow | Clinical management of chronic nightmares: imagery rehearsal therapy[END_REF] and was divided into 4 training sessions including teaching videos, exercises to practice at home and 4 face-to-face videoconferences with a psychologist. The first two sessions focused on cognitive restructuring of dysfunctional beliefs about nightmares, the third was dedicated to practicing visual mental imagery and managing intrusive images, and the fourth to transforming nightmares into dreams: participants were instructed to transform one nightmare per week without interacting with their psychologist, which could take up to 3 months, depending on the number of nightmares.

Participants completed questionnaires before, then 3 and 6 months after treatment: the Nightmare Frequency Questionnaire (NFQ), Nightmare distress (Sleep-50), Pittsburgh Sleep Quality Index (PSQI), Insomnia Severity Index (ISI), White Bear Suppression Inventory (WBSI), and Pichot Depression Scale (QD2A). The patients' perceived mastery over their nightmares was measured using the Specific Self-Efficacy Scale (SSES). The Working Alliance Inventory-Short Revised (WAI-SR) was completed during followup. Only patients whose nightmares had begun following a traumatic event completed the Post-Traumatic Stress Disorder Checklist Scale (PCLS) and Impact of Events Scale-Revised (IES-R).

All statistical analyses were carried out using Statistica v7.1. Three analyses of variance with repeated measurements including the intra-individual factor "Phase" (pre-treatment, post-treatment, and follow-up) were separately run on 3 interindividual factors: "Pathology" (with PTSD, n = 20, of which 10 with severe PTSD IES-R >53; without PTSD, n = 28), "Origin" (chronic nightmares following a traumatic event, n = 33; without traumatic event, n = 15), and "Type of trauma" (abuse during childhood, n = 11; sexual or physical assault, n = 11; road accident, n = 11). The sample size was determined with normal approximation using the z statistic for effect size [START_REF] Casement | A meta-analysis of imagery rehearsal for post-trauma nightmares: effects on nightmare frequency, sleep quality, and posttraumatic stress[END_REF]. Two hundred and three individuals were pre-registered and 127 assessed for eligibility, of which 67 individuals were retained for inclusion. Among these, 48 participants (36 ± 12 years, 83% women) completed the study and all questionnaires. Prior to the program, significant differences between participants with and without PTSD were found for sleep deterioration (p = 0.03) and depression (p = 0.01) (see suppl. data). PTSD severity (IES-R: p = 0.003; PCLS: p = 0.001) and effort of suppression (p = 0.014) were worse for patients who had been abused during childhood. Thought intrusion (p = 0.04) was weaker for road accident participants. The "Origin" factor was not significant before treatment.

The findings indicate that all outcomes improved between pretreatment and post-treatment (see online suppl. data). No significant difference was observed between post-treatment and followup. Effect sizes were comparable to face-to-face settings [START_REF] Casement | A meta-analysis of imagery rehearsal for post-trauma nightmares: effects on nightmare frequency, sleep quality, and posttraumatic stress[END_REF]: remote IRT reduced numbers of nights with nightmares (p < 0.001,d = 1.32), and sleep disturbance (p < 0.001, d = 0.9). 70% of participants experienced less than 3 nightmares per month at followup (it is below the pathological threshold). IRT also reduced insomnia (p < 0.001, d = 0.98): complete remission was observed in 33% of the 42 patients who had insomnia at inclusion. Remote IRT also reduced intrusive thoughts (p < 0.001, d = 0.57), suppression efforts (p < 0.001, d = 0.27), depression (p = 0.008, d = 0.35), and induced an increased feeling of control over dreams (p < 0.001, d = 0.9). Analysis of variance showed no significant interaction between the "Phase" and "Traumatic" factors. Remote IRT was as effective for PTSD patients as for nonpsychiatric participants. Whether the nightmares had begun following a traumatic event or not, and whatever the type of trauma, the clinical improvements were comparable. Remote IRT reduced all symptoms of PTSD (PCLS: p < 0.001, d = 0.37; IES-R: p = 0.006, d = 0.48) with the exception of avoidance (p > 0.05). Half of the PTSD patients reached a subpathological level by the end of treatment. The intensity of traumatic symptoms experienced by PTSD participants was reduced by an average of 25 ± 25%. The therapeutic alliance was equivalent for both groups.

In conclusion, this study enables us to generalize the positive results obtained from other telemedicine IRT studies on idiopathic nightmares [START_REF] Gieselmann | The Effects of an Internet-Based Imagery Rehearsal Intervention: A Randomized Controlled Trial[END_REF][START_REF] Lancee | Cognitive-behavioral self-help treatment for nightmares: a randomized controlled trial[END_REF] to traumatic nightmares with or without PTSD. According to the results, internet-based imagery rehearsal intervention combined with 4 videoconferences with a psychologist constitutes an effective first step, without any geographical constraints, in the treatment of PTSD patients.

Posttraumatic Stress Disorder: Using Remote Imagery Rehearsal Therapy to Treat Nightmares

	Benjamin Putois a, b Laure Peter-Derex b-d Wendy Leslie e Claire Braboszcz f Wissam El-Hage g,
	h Hélène Bastuji b, c
	a)Swiss Distance Learning University, Study Centre of Sierre,
	Sierre, Switzerland;
	b) Lyon Neuroscience Research Center,
	INSERM U1028, CNRS UMR 5292, Lyon, France;
	c) Sleep Medicine and Respiratory Disease Center, Croix-Rousse Hôpital, CHU of
	Lyon, Lyon, France;
	d) Lyon 1 University, Lyon, France;
	e) Clinical Health Psychology, University of Ulster, Ulster, UK;
	f) School of Psychological Science, University of Bristol, Bristol, UK;

g) CHU de Tours, Clinique Psychiatrique Universitaire, Tours, France; h) UMR 1253, iBrain, Université de Tours, Inserm, Tours, France

Acknowledgments

The authors thank all participants of the study, along with Dr. Higgins, Dr. Floccard, Dr. Faivre, the PROSOM association and the ABC Psychotrauma Association for their support. This study was funded by Fondation VINCI Autoroutes.

Statement of Ethics

The methodology respected sound ethical practice (French Clinical Trials Register: ANSM-2014-A00778-39; French Ethical Authorization: CPP No. 2014-A00778-39; Data Protection Authorization: CNIL No. 1612473).

Disclosure Statement

The authors declare no conflict of interest.


Denis Geraads
email: denis.geraads@evolhum.cnrs.fr

Cecile Blondel
email: cecile.blondel@univ-poitiers.fr

Hassane Taisso Mackaye

Andossa Likius
email: andossa.likius@yahoo.fr

Patrick Vignaud
email: patrick.vignaud@univ-poitiers.fr

Michel Brunet
email: michel.brunet@college-de-france.fr

Bovidae (Mammalia) from the lower Pliocene of Chad

The sites of Kossom Bougoudi (KB) and Kollé (KL) are intermediate in age between the Sahelanthropus sites of Toros Menalla and the Australopithecus sites of Koro Toro, and their bovid faunas are also intermediate in composition and stage of evolution. Four new taxa are erected. The hippotragine Tchadotragus fanonei nov. sp. is more derived than the type-species of the genus, from Toros Menalla. Kobus ammolophi nov. sp. is also clearly related to the most common reduncine of the latter sites, rather than with other African forms. However, Jamous kolleensis nov. gen. nov. sp., a new bovine with extremely divergent, horizontal horn-cores, is unrelated to other Chadian Bovini. The KB and KL assemblages document the gradual replacement of hippotragines by alcelaphines in Northern Chad, but it is not necessarily linked with environmental change, as all Chadian assemblages virtually lack indicators of bush or woodland like Tragelaphini and Aepyceros. In spite of a significant endemic component, the KB and KL Bovidae compare best with some of those from Sahabi in Libya, confirming North-South connections.

INTRODUCTION

The main sets of fossiliferous localities where the "Mission Paléoanthropologique Franco-Tchadienne" has been conducting paleontological field research in the Djurab region of Northern Chad since 1994 are 1) the middle Pliocene of Koro-Toro (KT), with the first australopithecines west of the Rift [START_REF] Brunet | The first australopithecine recovered west of the Rift Valley (Koro Toro region, Republic of Chad)[END_REF][START_REF] Brunet | Australopithecus bahrelghazali, une nouvelle espèce d'Hominidé ancien de la région de Koro Toro (Tchad)[END_REF], whose age was estimated by biochronology at 3-3.5 Ma; 2) the lower Pliocene of Kollé (KL) with an estimated age of 4-4.5Ma [START_REF] Brunet | Tchad: découverte d'une faune de Mammifères du Pliocène inférieur[END_REF]; 3) the lowermost Pliocene of Kossom Bougoudi (KB), with an estimated age of ca.5.5Ma [START_REF] Brunet | Chad: discovery of a vertebrate fauna close to the Mio-Pliocene boundary[END_REF]; and 4) the upper Miocene of Toros-Menalla (TM), which yielded the earliest known hominid, at ca. 7Ma [START_REF] Vignaud | Geology and Palaeontology of the Upper Miocene Toros Menalla hominid locality, Chad[END_REF][START_REF] Brunet | A new Hominid from the Upper Miocene of Chad, Central Africa[END_REF][START_REF] Brunet | New material of the Earliest Hominid from the Upper Miocene of Chad[END_REF]. These ages have been confirmed by radiometric dating [START_REF] Lebatard | Cosmogenic nuclide dating of Sahelanthropus tchadensis and Australopithecus bahrelgazali: Mio-Pliocene hominids of Chad[END_REF].

As is usual in African faunas of these periods, the Bovidae make up a large proportion of the fauna. Those from Koro-Toro have been described previously [START_REF] Geraads | Pliocene Bovidae from the Koro Toro Australopithecine sites, Chad[END_REF]; some of those from Toros-Menalla have been published [START_REF] Geraads | New Hippotragini (Bovidae, Mammalia) from the Late Miocene of Toros-Menalla (Chad)[END_REF], while the remaining specimens currently are under study. We describe here those from Kossom Bougoudi and Kollé. This material is not as well preserved as that from KT or TM. Most specimens consist of isolated teeth, or incomplete horn-cores and limb bones, and almost all of them suffered wind abrasion, obscuring some anatomical details, and introducing some uncertainties in the measurements.

The main localities from the KB area (N 16°20', E 18°40') are KB3, KB4 and KB7, which are all close to each other and were even lumped together during some field campaigns. These localities yield a homogeneous faunal assemblage and are referred to collectively as "KB" here. Other KB localities are much poorer. The bovids from KB15, KB16, KB18, KB22, and KB26 suggest that these localities could be of the same broad age as the main ones, and this is probably true also of other KB localities, except KB24 which is much younger. The Kollé sites (N 16°20', E 19°00') are also located very close to each other, and nothing suggests that they are diachronic.

halshs-00433315, version 1 -18 Nov 2009

All specimens belong to the "Département des Collections" of the Centre National d'Appui à la Recherche (CNAR), N'Djamena, Chad. Authors of family-group names are given according to [START_REF] Grubb | Review of family-group names of living bovids[END_REF], and when describing cranial material the skull is oriented so that the tooth row is horizontal.

Abbreviations-APD: antero-posterior diameter; TrD: transverse diameter; HC: horn-core.

SYSTEMATIC PALEONTOLOGY

Bovidae from Kossom Bougoudi

Family BOVIDAE Gray, 1821 Sub-family BOVINAE Gray, 1821 Tribe BOVINI Gray, 1821 Bovini gen. et sp. indet. This tribe is represented at KB by some post cranial elements, two small horn-core fragments, KB3-98-090 and KB3-97-003, a lower molar KB7-97-009, an m3 KB3-98-106, and a fragment of mandible KB3-98-042; the length of both m3s at mid-height is 43.5 mm. Since all teeth are mandibular, they cannot be directly compared with those from Kollé (see below), but they are roughly at the same evolutionary stage, being decidedly more bovine-like than those of S. demissum from Langebaanweg.

There is no goat-fold but a strong parastylid, the labial pillars are pinched, the lingual pillars well rounded, but the ectostylid is not larger than in the latter site; the least worn m3 has a distal flange and a small fossette in the third lobe. They are slightly larger than the bovine teeth from Toros-Menalla, and the parastylid is stronger. Unfortunately, lack of significant cranial or horn-core remains precludes generic assignment of the KB bovine. Genus TCHADOTRAGUS [START_REF] Geraads | New Hippotragini (Bovidae, Mammalia) from the Late Miocene of Toros-Menalla (Chad)[END_REF] Type-species-Tchadotragus sudrei Geraads et al., 2008, from Toros-Menalla. Diagnosis-A primitive hippotragine of medium size, with a braincase slightly or only moderately inclined on the splanchnocranium and broad over the mastoids, both halves of occipital surface facing partly laterally, a basioccipital with strong anterior tuberosities, large orbits with very prominent rims, a short face with a small jugal and a short and deep lacrymal bone, a large diffuse anteorbital fossa, a relatively large ethmoidal fissure, premaxillae not contacting nasals, long slender curved horn-cores with some sigmoid curvature in antero-dorsal view, usually without transverse ridges, uprightly inserted and close to the midline, a large sinus in the pedicle, rather small supraorbital foramina, molar pattern simpler than in modern hippotragines, and premolars neither shortened nor enlarged (type-species description slightly modified after [START_REF] Geraads | New Hippotragini (Bovidae, Mammalia) from the Late Miocene of Toros-Menalla (Chad)[END_REF].

TCHADOTRAGUS FANONEI nov. sp. aff. Protoryx sp. in [START_REF] Brunet | Chad: discovery of a vertebrate fauna close to the Mio-Pliocene boundary[END_REF] Holotype-KB3-97-146, left part of a brain-case with incomplete horn-core (Fig. 1B).

Paratype-KB3-97-200, frontlet with complete horn-cores, both halves of the mandible (the right one with complete tooth-row), tibia and talus (Fig. 1A, C, D; 2A; 3A).

Referred Specimens-About 60 specimens are definitely identified from KB3, KB4, KB7, and one from KB22, but most medium-large size bovids from these and other sites in the KB area are probably also of this species, which is the most common bovid there.

Derivatio Nominis-In memory of our colleague Fanoné Gongdibé.

Diagnosis-A species of Tchadotragus differing from the type-species by horn-cores with a longer pedicle, stronger cranio-facial angle (as shown by the anterior border of the horn-core pedicle more in line with the horn-core itself), longer and narrower neurocranium, and better expressed goat folds on lower molars.

halshs-00433315, version 1 -18 Nov 2009

Description and Comparisons-The holotype is the only specimen preserving part of the braincase, which is slightly longer (length from front of pedicle to top of occipital = 161 mm vs. 138-147 mm, mean 142 mm, N = 3, in T. sudrei), higher (occipital height, from top of foramen magnum = 50 mm vs. 40-48 mm, mean 43 mm, N = 6, in T. sudrei) and narrower (width over mastoids = ca. 96 mm vs. 94-120 mm, mean 107 mm, N = 9, in T. sudrei) than at Toros-Menalla. This difference in braincase proportions is reflected in the closer approach of the poorly defined temporal lines posteriorly, in the narrower supra-occipital bone, both sides of the occipital facing still more laterally, and more lengthened basicranium and basioccipital. It may be that the anterior tuberosities of the basioccipital reached the level of the missing foramen ovale, in contrast to the type-species, and this character has accordingly been removed from the generic diagnosis. We regard all these differences as significant, as the single T. fanonei specimen stands apart from all T. sudrei specimens.

As in T. sudrei, the horn-cores of the types are very uprightly inserted (their posterior border makes an angle of about 95° with the parietal profile in lateral view), slightly divergent, with an incipient anticlockwise torsion on the right horn-core, and a strong backward curvature. The latter is less clearly localized around mid-length than in T. sudrei, but too few specimens are known for this apparent difference to be included in the diagnosis; in some distal fragments (e.g., KB3-97-238 and KB3-97-070), the curvature is more localized near the tips, showing that these horn-cores were not very long. Other specimens consist mostly of basal parts. Together with the types, they all show that the pedicle is longer than at TM, so that its lateral side is less deeply concave in front view. This difference is increased by the slightly less prominent orbital rims, although none is completely preserved at KB. Other consequences of the pedicle being longer are that the supra-orbital foramen is farther away from the horn-core, and that the front edge of the pedicle is almost straight and in line with that of the horncore itself in lateral view, instead of being concave in T. sudrei. However, this is also because the face is more inclined in respect to the brain-case, and the angle between the facial profile and the horn-core would have been larger. It may also be that the maximum diameter of the cross-section is located less 6 halshs-00433315, version 1 -18 Nov 2009 posteriorly than at TM (Fig. 2A-C), but the difference in this regard between the left and right horncores of KB3-96-056 makes us cautious about the validity of this difference.

Horn-core measurements are virtually identical with those from TM (mean APD x TrD: 48.1 x 35.4 mm for 12 specimens from KB, vs. 48.1 x 35.7 mm for 55 specimens from TM).

The teeth do not differ much from those of T. sudrei from Toros-Menalla. Neither the morphology, nor the hypsodonty, measurements, nor premolar/molar proportions of the few complete specimens differ significantly (Table 1).

The p4 has a poorly distinct paraconid, widely separated from the bulbous metaconid. On the molars, the ectostylid is moderate but, on the average, the goat fold is definitely stronger than at TM, where it is incipient, at most. Here, it varies from completely absent to rather strong, but never reaches the top of the crown.

The post-cranial skeleton is best illustrated by associated elements KB7-97-050, the paratype tibia KB3-97-200, and several other short bones and fragments. The distal articulation of the humerus corresponds to our second type at Toros-Menalla [START_REF] Geraads | New Hippotragini (Bovidae, Mammalia) from the Late Miocene of Toros-Menalla (Chad)[END_REF]. It resembles modern hippotragines, but is less cylindrical. Measurements (Table 2) are also very similar to those from TM.

On the radius, the palmar outline of the proximal surface is not sharply broken, the lateral tuberosity is of moderate size, and the distal extensor grooves are slightly concave; all these features are found in modern hippotragines. On the metacarpal, the lateral sides of the distal condyles are moderately divergent, as in modern hippotragines, but in contrast to them, the unciform facet is not much lower than the capitato-trapezoid facet, and the epiphysis is not depressed just above the condyles. The femur is represented by the shaft only. Accounting for the slightly larger available measurements of KB3-97-200 compared to KB7-98-050, the tibia is about one tenth longer than the radius, a difference comparable with modern hippotragines (Gentry & Gentry, 1978, fig.19), but smaller than in alcelaphines, and larger than in reduncines or tragelaphines. The central distal process of the tibia is narrower than in tragelaphines and alcelaphines, and the anterior fibular facet is offset medially, as at 7 halshs-00433315, version 1 -18 Nov 2009 TM and in modern hippotragines (Fig. 1A). Although the post-cranial skeleton from KB can be referred definitely to Tchadotragus, it does not solve the problem of postcranial identification at TM [START_REF] Geraads | New Hippotragini (Bovidae, Mammalia) from the Late Miocene of Toros-Menalla (Chad)[END_REF]. Dimensions of the talus, the most common bone, cover the whole range of those of the larger antelopes at TM, falsifying the idea that Saheloryx averages larger than Tchadotragus. Thus, it could be that the former is illustrated by the first type of humeri that we recognized [START_REF] Geraads | New Hippotragini (Bovidae, Mammalia) from the Late Miocene of Toros-Menalla (Chad)[END_REF], and by some tibiae without offset anterior fibular facet; this would confirm our hypothesis that Saheloryx is less closely related to modern hippotragines than is Tchadotragus.

There is no doubt that T. fanonei is closely related to T. sudrei, and it is tempting to believe that it is its descendant. The longer horn-core pedicle, greater cranial flexure, and stronger goat-folds are more derived, and the younger geological age of the former does not contradict this succession. It would follow that other cranial differences, the proportions of the braincase and the orientation of the occipital, are also derived in T. fanonei, but they draw it farther away from modern hippotragines, confirming that Tchadotragus is a distinct lineage.

Dentitions similar to those of Tchadotragus are present at Kanapoi (KNM-KP29274, KP29276, and KP29279; the latter two specimens were referred to the Reduncini by [START_REF] Harris | Early Pliocene Tetrapod remains from Kanapoi, Lake Turkana Basin, Kenya[END_REF], but they might as well be hippotragine). Of the horn-cores from Lothagam referred to Hippotragus sp. by [START_REF] Harris | Bovidae from the Lothagam succession[END_REF], some (like KNM-LT23598) are too obliquely inserted for this genus, but LT23131, as well as LT23709, both from the Upper Nawata, referred to Praedamalis by Harris, could belong to the modern genus or to Tchadotragus, but are too incomplete for detailed comparisons. Referred Material-About 40 specimens definitely can be assigned to this species, and some postcranials must belong here too. Besides the type, the best specimen is KB3-97-171, a less well preserved braincase with left horn-core. KB7-97-088 is a right tooth-series p4-m3 (Fig. 3C), KB7-97-095 a left series m2-m3, and KB7-97-098 right and left P2-M3 (Fig. 3B), all presumably of the same individual.

Derivatio Nominis-Because sand dunes (Greek αμμόλοφος) are widespread in the Djurab desert.

Diagnosis-A species of Kobus of medium size. Horn-cores small, upright, with a moderate divergence which increases upwards, with little compression and backward curvature, and no transverse ridges. Braincase with a flat dorsal profile, mastoid exposure with a distinct mastoid process.

Teeth of advanced reduncine morphology, Description-On KB3-97-154, the cranial flexure was similar to that of K. kob. The supraorbital foramina open directly into the orbit; they are incompletely preserved but it seems that the frontal depression around them was rather shallow. The fronto-parietal suture is almost straight, with only a very shallow median indentation. The post-cornual fossa is small and shallow. The horn-cores are very short compared to the size of the braincase, although complete fusion of the basisphenoidbasioccipital suture shows that the specimen was fully adult. They are inserted uprightly in side view (the angle between the base of their posterior edge and the top of the braincase is about 75°), slightly curved backwards for most of their length but are straight or even have a weak forward curvature near the tip. The divergence is moderate (about 55°) and increases upwards. The cross-section is oval (Fig. 2F,G), with no tendency towards a postero-lateral keel, and is moderately compressed near the base but less so distally. Its main axis makes an angle of about 45° to the sagittal plane, and the maximum transverse diameter is closer to the anterior side. There are no transverse ridges.

The braincase has an almost flat dorsal profile and widens posteriorly. The temporal lines are indistinct because of weathering, but seem to approach closely posteriorly, on either side of a narrow supra-occipital. The occipital is broad, with a triangular rather than semi-circular outline, and its sagittal part is slightly raised above the lateral sides, which face somewhat laterally. The mastoid exposure faces postero-laterally; it is triangular and broadens regularly from its dorsal tip around the small mastoid foramen to its ventral base. A vertical blunt ridge marks the limit between a posterior concave part, which belongs more to the occipital plane, and an anterior one which ends ventrally by forming a distinct rather large mastoid process, the tip of which is broken. The cranial base is not preserved, except for part of the basioccipital, showing posterior tuberosities not wider than the very incompletely preserved anterior ones.

On KB3-97-171, the horn-core is slightly larger and longer and was slightly more divergent from its counterpart (about 60°) but the divergence increases very little upwards. The auditory bulla (not preserved on KB3-97-154) is large and inflated, but the rest of the braincase is similar to that of the previous specimen. Measurements are given in Table 3.

Other horn-cores are mostly incomplete and weathered. They confirm the above-mentioned features; however, some may show a tendency towards flattening of the lateral side, a tip slightly curving forwards, or a deeper post-cornual fossa.

The teeth have a modern reduncine pattern. On the upper ones, the lobes are well outbowed between the styles, the entostyle is transversely lengthened, and the protocone is pinched lingually.

Corresponding features can be seen on lower teeth, and the goat fold is long. On KB7-97-088, the paraconid and parastylid of p4 are fused into a narrow blade up to the top of the crown, but they were probably distinct on KB4-97-001, where they are broken; on the three available p4s, this anterior complex remains widely separated from the metaconid, and the talonid is antero-posteriorly compressed with a hypoconid strongly salient labially. The lengths of the upper premolar and molar 10 halshs-00433315, version 1 -18 Nov 2009 series of KB7-97-098 are 33.5 and 53.5 mm, respectively. Those of the lower molar series of KB7-97-088 and KB4-97-008 are 56.5 and 53 mm, respectively.

Comparisons-There are two species of Kobus at Koro-Toro. Kobus korotorensis [START_REF] Geraads | Pliocene Bovidae from the Koro Toro Australopithecine sites, Chad[END_REF] is mostly known by its horn-cores; their basal divergence is comparable to that of the KB Kobus, but it strongly decreases upwards. The cross-section is also different, being more triangular, with a flattened postero-medial surface. The second species, K. tchadensis Geraads et al., 2001, has very long and very divergent horn-cores with a circular cross-section, the face is much less bent on the cranium, and the ventral part of the mastoid is much narrower, the mastoid process being much smaller. Thus, the most common species of Kobus at KB has no close relationship with the KT ones. Some reduncine specimens from TM, instead, are clearly related to the KB species. They share a similar length, orientation, course, and cross-section of the horn-cores, similar braincase size and morphology, including a wide occipital, straight dorsal profile, large mastoid exposure with a welldeveloped mastoid process, and a frontal much bent along the midline. Differences are that the KB horn-cores are on the average slightly larger and less compressed, slightly more divergent, and the main axis of the cross section is more inclined in respect to the midline, but the main difference is in the shape of the mastoid exposure, which is shorter dorsally and more triangular, whereas its squamosal and occipital sutures are more nearly parallel at TM. From sites outside Chad, only a few reduncines of medium or large size have horn-cores short enough to be compared to the KB species. Kobus subdolus Gentry, 1980, from Langebaanweg, has horn-cores with a similar degree of compression and a similar course in lateral view; its braincase also widens posteriorly, has a flat upper profile, and no indentation of the parieto-frontal suture. It differs first by its much more primitive teeth, but also in that the horn-cores are usually slightly larger, with a flattened lateral surface, are inserted more obliquely and with the main axis of the cross-section seemingly less angled in respect to the sagittal plane, and with a weaker basal divergence which 11 halshs-00433315, version 1 -18 Nov 2009 decreases upwards; its occipital faces wholly posteriorly and includes most of the mastoid exposure, which is small. Another species from Langebaanweg (Kobus sp.2 of [START_REF] Gentry | Fossil Bovidae (Mammalia) from Langebaanweg, South Africa[END_REF] has more divergent and more curved horn-cores, the top of the braincase is convex, and the posterior ridges on the basioccipital are more transversally elongated.

The horn-cores of the Kobus aff. subdolus from the earliest Pliocene of Tinde at Manonga [START_REF] Gentry | Fossil Ruminants (Mammalia) from the Manonga Valley, Tanzania[END_REF] are on average slightly less compressed, less curved and more divergent than those from KB, but similar in their increasing divergence upwards. Its teeth are more primitive than those from KB because of the weaker labial ribs of the paracone and metacone, the lack of pinching of the protocone, weak or absent basal pillars, weaker goat folds and short disto-lingual arm of the hypoconid on p4. [START_REF] Wells | Fossil Bovidae from the Limeworks Quarry, Makapansgat, Potgietersrus[END_REF], from Makapansgat is a species of small size, with massive horn-cores with a similar divergence and antero-lateral to postero-medial compression, but they are extremely short. The skull has not been described in detail, but the dorsal cranial profile looks more rounded, and the occipital condyles protrude less, posteriorly, meaning that the occipital is more in a single plane. [START_REF] Lehmann | Fossil Bovidae (Mammalia) from the Mio-Pliocene of Sahabi, Libya[END_REF] described as Redunca aff. darti two frontlets and a horn-core from an unknown level of Sahabi, Libya. They differ mainly from the KB fossils by their larger size and presence of transverse ridges on one specimen but nothing is known of the skull. [START_REF] Harris | Bovidae from the Lothagam succession[END_REF], from Lothagam, is about the same size as Kobus ammolophi but the horn cores have a distinct sigmoid curvature so that the divergence diminishes upwards, the supra-orbital foramina are more triangular and narrower, the braincase has a convex dorsal profile, the occipital is narrower, and the mastoid exposure is wholly lateral, with an anterior expansion behind the auditory foramen; these differences show that they are distinct species.

Redunca darti

Kobus presigmoidalis

Kobus ammolophi differs from K. porrecticornis from the upper part of the Dhok Pathan Formation of the Siwaliks, and from related forms from Lukeino (Thomas, 1979) and the Baard's Quarry at Langebaanweg [START_REF] Gentry | Fossil Bovidae (Mammalia) from Langebaanweg, South Africa[END_REF] by its larger size and more upright horn cores, the divergence of which increases upwards rather than remaining constant or decreasing.

Kobus khroumirensis [START_REF] Arambourg | Vertébrés villafranchiens d'Afrique du Nord[END_REF] is based upon a poorly preserved incomplete braincase from Lake Ichkeul, an early Pliocene site in Tunisia. It is slightly larger, the occipital is relatively still lower, the dorsal braincase profile is more convex, but the mastoid exposure is similar, with a depressed posterior part in the occipital plane, and an incipient mastoid process anteriorly. A detached horn-core has a similar divergence that increases upwards, a similar cross-section whose major axis is strongly angled on the sagittal plane, but has a slight forward curvature.

The teeth of Kobus ammolophi are much more derived than those of Kobus subdolus Gentry, 1980, from Langebaanweg. However, as noted by Gentry, the latter are remarkably primitive for their geological age, and more typical reduncine teeth are known as early as the late Miocene in the Middle Awash (Haile-Selassie, 2001), at Lukeino and Mpesida [START_REF] Thomas | Les Bovidés du Miocène supérieur des couches de Mpesida et de la Formation de Lukeino (district de Baringo, Kenya)[END_REF], and in the early Pliocene of the Nkondo Formation of Uganda [START_REF] Geraads | Geology and Palaeobiology of the Albertine Rift Valley Uganda-Zaire[END_REF]. The fact that dental morphology evolved at different rates in the various reduncine lineages is confirmed by Kobus sigmoidalis from Olduvai, where the labial pillars of upper molars are only weakly rounded [START_REF] Gentry | Fossil Bovidae (Mammalia) of Olduvai Gorge, Tanzania. Part I. 28 halshs-00433315, version 1 -18[END_REF]. Therefore, it would be premature to draw any biochronological conclusion from the morphology of the KB teeth.

KOBUS cf. KOROTORENSIS Geraads et al., 2001

Description-KB3-98-038 and KB4-97-031 are two heavily weathered horn-cores whose cross-section outline is too different from that of Kobus ammolophi for them to be included in the same species, and they are more like K. korotorensis from Koro-Toro [START_REF] Geraads | Pliocene Bovidae from the Koro Toro Australopithecine sites, Chad[END_REF]. Their anteroposterior as well as transverse diameters are in the 30-32 mm range, but cannot be precisely measured.

At least KB4-97-031 was more inclined than in the latter species, but too little is preserved of their bases for their divergence to be estimated. Their cross-section has the shape of a rounded triangle, but 13 halshs-00433315, version 1 -18 Nov 2009 the lateral side is narrower than at Koro-Toro, so that one of the adjoining surfaces is posterior rather than postero-medial. We provide no definite identification for these specimens.

Sub-family ANTILOPINAE Gray, 1821

Tribe AEPYCEROTINI Gray, 1872 Genus AEPYCEROS Sundevall, 1847

AEPYCEROS sp.

Description-There are only two definite Aepyceros specimens at KB: KB3-97-361, a crushed and deformed frontlet, but with the base of the left horn-core well-preserved (APD = 37.8 mm; TrD. = 36.2 mm), and KB3-97-081, the weathered base of a right horn-core; KB7-97-130 and KB3-97-247 are doubtful horn-core fragments. On KB3-97-361, the frontal is poorly preserved, but it was not thickened as in the modern impala, and sinuses were much reduced or absent; nothing can be said about the supra-orbital foramina or post-cornual fossa. The horn-cores are large relative to the size of the frontal; at the base their angle of divergence is about 70°, but it increases upwards for about 10 cm before decreasing; they also have a regular backward curvature in side view, and therefore a clear normal torsion. The cross-section at the base is almost circular, with only a hint of a postero-lateral keel underlined by a shallow groove; there is only a slight indication of transverse ridges. KB3-97-081 differs from Kobus by its smaller size and weaker compression, weak but distinct spiralling, and presence of sinus in the frontal bone.

Comparisons-The reduced or absent pneumatization rules out the inclusion of KB3-97-361 in

A. melampus, while the clear spiral of the horn-cores differs from several unnamed middle Pliocene forms, such as those from Hadar or from the oldest Omo sediments. Aepyceros shungurae from the Turkana basin may have more clearly spiralled horn-cores, but they are smaller. The KB Aepyceros horn-cores best match those of A. premelampus [START_REF] Harris | Bovidae from the Lothagam succession[END_REF], from Lothagam, except that the latter are almost always more compressed; [START_REF] Harris | Bovidae from the Lothagam succession[END_REF] noticed that their size decreases through the Lothagam sequence, and KB3-97-361 is larger than all those from the Apak Member, and close to the largest specimens of the Nawata Fm. However, we prefer not to attribute these specimens to species, as the evolution of Aepyceros is still poorly understood, with several lineages co-existing in the Pliocene of Africa.

Tribe ANTILOPINI Gray, 1821 Genus GAZELLA Blainville, 1816 GAZELLA sp. A Material-KB3-97-009 is a mandible with the labial walls of m2-m3 and the alveoli of other teeth. No Antilopini horn-cores are known from KB.

Description and Comparisons-The third lobe of m3 is large, but shorter than the other two; the premolar series includes a two-rooted p2, and is rather long (estimated length = 22.5 mm ± 0.5 mm, vs. ca 44 mm for the molars). A specimen of similar premolar length, but with longer molars, was referred by [START_REF] Geraads | Pliocene Bovidae from the Koro Toro Australopithecine sites, Chad[END_REF] to an Antidorcas with primitive, long premolars. We believe that those of the present specimens are too long for this genus.

GAZELLA sp. B ?

Material-KB3-98-012 is a mandible fragment with m2-m3 (estimated length m1-m3 = 35 mm), KB26-97-001 is a mandible with p4-m3 (length m1-m3 = 38).

Description and Comparisons-These specimens indicate smaller animals than KB3-97-009, and we tentatively refer them to another species, which could be close to a species from TM.

Bovidae from Kolle

Sub-family BOVINAE Gray, 1821 Tribe BOVINI Gray, 1821 Genus JAMOUS nov. gen.

Type-species-Jamous kolleensis nov. sp.

Diagnosis-That of the single species

Derivatio Nominis-Arabic ,ﺟﺎﻣﻮس buffalo.

JAMOUS KOLLEENSIS nov. sp.

Simatherium sp. in [START_REF] Brunet | Tchad: découverte d'une faune de Mammifères du Pliocène inférieur[END_REF] Holotype-KL3-96-013, skull lacking the left part of the face, front of the muzzle and premolars; three horn-core segments found nearby have a quite satisfactory fit onto the skull and are taken as being part of the holotype (Figs. 2E,4).

Type-locality-Locality KL3, Kollé, Djurab Erg, Chad.

Diagnosis-A bovine with horn-cores of moderate length and almost without curvature, inserted horizontally above the post-orbital bar, almost completely divergent, not much compressed dorso-ventrally, with a rounded triangular cross-section, the antero-dorsal and antero-ventral edges being almost keel-like, and a slightly concave postero-ventral face. Face short and deep, no frontal bosses or rugosities, parietal depressed and separated by a transverse thick ridge from the supraoccipital which is not fully deflected into the occipital plane.

Derivatio Nominis-From Kollé, the area of the type-locality.

Description-The holotype skull is that of an adult with well-worn M3. The sutures are not traceable, and most of the bone surface is weathered, but the skull is not distorted. The face was deep, as shown by what remains of the right maxilla, M3 being far below the orbit. The dorsal edge of the maxilla is blunt, suggesting that it had no contact with the missing nasal, and that at least a remnant of ethmoidal fissure might have been present. There is no sign of a pre-orbital fossa. The lateral palatal notches reach the level of the middle of the second lobe of M3, while the choanae are more caudal than M3. The vomer is not visible in the nasal fossae, and was thus widely separated from the palate. The 16 halshs-00433315, version 1 -18 Nov 2009 lateral border of the masseter insertion forms a tubercle under the orbit, but the zygomatic arch is otherwise lightly built. The orbital border is only slightly raised above the plane of the maxilla, and the orbital rim is not tubular as in some bovines, such as Bison. The supra-orbital foramina are small and moderately wide apart. Between them, the frontals are slightly depressed on either side of the sagittal suture, but between the horn-cores the frontal is transversely flat. There is no sign of frontal boss or rugosities. The horn-cores were inserted above the post-orbital bar and partly overhang the orbits, in a position not more caudal than in many antelopes. The detached right horn-core has some missing parts around the base, but the left one fits closely onto the skull, especially along the temporal fossa, ensuring that all four specimens belong to the same individual. The horn-cores emerge transversally from the skull, almost horizontally, and diverge by an angle of about 170° (both in anterior and dorsal views). Although the front part of their base is above the orbits, they extend well behind it, so as to cover most of the temporal fossa. They are not much dorso-ventrally compressed, and the cross-section is that of a rounded triangle, with an anterior dorsal keel, an antero-ventral one (the primitive posterolateral keel), and a rounded posterior border. The dorsal face of the left horn-core is eroded, but on the right one it was more convex than the other two, the postero-ventral face being flattened or even slightly concave near the base, reminiscent of some Pliocene East-African bovines. The base of the distal fragment shows that towards the tip, the section becomes more compressed and more oval, and that the horn-cores, although broad at the base, were not very long compared to the size of the skull.

The two specimens together indicate that the horn-core was virtually straight, with only a hint of downward curvature basally, and a slightly stronger upward and backward curvature distally. The frontal sinus extends into the first few centimeters, but the right horn-core shows no more sinus at 8 cm above the base, showing that pneumatization was limited to the base.

Between the horn-cores, the frontal is significantly arched antero-posteriorly (Fig. 4A), but this convexity abruptly ends with a small tubercle at the level of the posterior horn-core border (presumably the limit between the frontal and parietal bones), where the profile becomes concave for 35 mm. Thus, the parietal was relatively long for a bovine. Behind this, a thick, raised, well-delimited ridge (ca. 28 x 68 mm) extends almost from one temporal fossa to another, where they come closest to each other, but still remain far apart. Further back, the supra-occipital area forms a well-delimited trapezoidal area, at an angle to both the parietal and occipital planes. Although it is not easy to measure precisely, the distance between the horn-core and this supra-occipital area is short, but this is due to the large size of the horn-core base, not to their backward shift. The occipital proper is broad, with a straight dorsal edge separating it from the supra-occipital. The mastoid exposure looks narrow, and its ventral part faces ventro-laterally. The left paroccipital process is directed ventro-caudally and is transversely compressed, but perhaps eroded. The basioccipital is triangular, as is usual in bovines, and long compared to its width over the posterior tuberosities; the poorly expressed (but eroded) anterior tuberosities reach the level of the small oval foramen. The bulla is oval and well inflated.

The premolars and the buccal walls of the molars are missing. The central valleys of the latter are simple, without extremely rounded pillars of the labial lobes as in derived bovines, and only small enamel spurs; the lingual lobes are angular, especially the protocone; there is a central enamel island, and a strong entostyle, Y-shaped on M3. The molars are large compared to the size of the skull.

Measurements of the skull and horn-cores are given in Table 4.

The only other bovine remains from Kollé are a few weathered tali.

Comparisons-The Bovini are relatively uncommon elements of the late Miocene and Pliocene

African faunas. Brabovus nanincisus Gentry, 1987, from Laetoli, is a small species with Cephalophuslike horns totally unlike the Kollé bovine. Pelorovis, from the late Pliocene and Pleistocene of East and perhaps North Africa, has forward curving and/or extremely long horn-cores with an oval cross-section, and is also quite unlike the Kollé bovine. Other taxa form a complex group within which relationships are hard to decipher. Following the taxonomy of [START_REF] Gentry | A new bovine (Bovidae, Artiodactyla) from the Hadar Formation, Ethiopia[END_REF], they include Ugandax demissum [START_REF] Gentry | Fossil Bovidae (Mammalia) from Langebaanweg, South Africa[END_REF], from the early Pliocene of Langebaanweg, perhaps also present in Uganda [START_REF] Geraads | Geology and Palaeobiology of the Albertine Rift Valley Uganda-Zaire[END_REF]; Ugandax coryndonae [START_REF] Gentry | A new bovine (Bovidae, Artiodactyla) from the Hadar Formation, Ethiopia[END_REF], from the middle Pliocene of Hadar; Ugandax gautieri [START_REF] Cooke | Pleistocene Mammals from the Kaiso Formation and other related deposits in Uganda[END_REF], from Kazinga, Uganda, whose age is not precisely known but might be close to 5 Ma. (Pickford et al., 1993: 104); Simatherium kohllarseni Dietrich, 1941, from the middle Pliocene of Laetoli [START_REF] Dietrich | Ältestquartäre Säugetiere aus der südlichen Serengeti, Deutsch-Ostafrika[END_REF][START_REF] Dietrich | Fossile Antilopen und Rinder Äquatorialafrikas[END_REF][START_REF] Gentry | Pliocene Bovidae from Laetoli[END_REF] and perhaps also Koobi Fora [START_REF] Harris | Family Bovidae[END_REF]; and Simatherium shungurense Geraads, 1995, from the late Pliocene of Omo.

They have horn-cores that are usually massive but not very long (compared to skull size), are inserted above the back of the orbits or slightly behind them, are moderately to strongly inclined in side view, but never horizontally (dorso-ventral crushing probably increased their inclination in the holotype skull of S. shungurense), and are more divergent than in most antelopes, but never extremely so, and the divergence lessens distally. They are not much compressed medio-laterally (i.e., dorso-ventrally if very divergent), with a cross-section which is not neatly triangular, because the three faces are usually convex, but they may have a more or less marked anterior keel, and the position of the primitive postero-lateral keel may sometimes be discerned. According to the results of Gentry's cladogram (2006), a shift in the position of the postero-lateral keel towards a more anterior position would characterize Syncerus which includes, besides the living African buffaloes (S. caffer), Syncerus acoelotus [START_REF] Gentry | Fossil Bovidae (Mammalia) of Olduvai Gorge, Tanzania. Part I. 28 halshs-00433315, version 1 -18[END_REF], from Olduvai, a Syncerus sp. from Omo Shungura Mb. C [START_REF] Gentry | The Bovidae of the Omo deposits, Ethiopia[END_REF], and, to remain monophyletic, both species of Simatherium. Although one might argue about the robustness of such parsimony analyses (see [START_REF] Geraads | Phylogenetic analysis of the tribe Bovini (Mammalia, Artiodactyla)[END_REF][START_REF] Geraads | Simatherium shungurense n.sp. un nouveau Bovini (Artiodactyla, Mammalia) du Pliocène terminal de l'Omo (Ethiopie)[END_REF] for alternative results), it is clear that none of the species referred to Simatherium or Ugandax has horn-cores as divergent as the Kollé form. Since the Kollé faunal assemblages are of early Pliocene age, comparisons can be made primarily with the Uganda Nkondo faunas and the late Miocene Middle Awash faunas [START_REF] Haile-Selassie | Late Miocene Mammalian fauna from the Middle Awash valley, Ethiopia[END_REF]. A skull fragment from Nkondo, referred to Simatherium aff. demissum by [START_REF] Geraads | Geology and Palaeobiology of the Albertine Rift Valley Uganda-Zaire[END_REF] has an almost flat dorsal profile, and horn-cores which were less divergent. In the Middle Awash, horn-cores fragments from Asa Koma and Kabanawa, dated to ca. 5.5 Ma, were also more uprightly inserted (Haile-Selassie, 2001, Fig.5.37) than at Kollé. The same is true at least of the most complete of the Lothagam specimens, KNM-LT 23724. An unpublished relatively complete skull from Lissasfa, Morocco, well-dated to ca. 5.5 to 6 Ma. [START_REF] Raynal | Contribution du site paléontologique de 30 halshs-00433315, version 1 -18 Nov 2009 Lissasfa (Casablanca, Maroc) à une nouvelle interprétation du Mio-Pliocène de la Méseta[END_REF], also displays horn-cores which are only moderately divergent and inclined. Last, the poorly known bovine from Toros-Menalla has a long braincase and moderately divergent horn-cores, and is also very different from the Kollé one.

The teeth of the Kollé bovine are larger than those from Lukeino (Thomas, 1980, fig. 1.3) and the entostyle is stronger; they differ by the same characters from those of Toros-Menalla. They are also more modern-looking than the very primitive teeth of S. demissum of Langebaanweg, but not than those of the Lothagam bovine, which are quite advanced, in spite of their early age.

The modern Syncerus is represented today by a wide morphocline ranging from the large South-African Cape buffalo to the small forest buffalo of Central Africa. The former has large horns emerging from frontal bosses that can be huge in the males, and are directed transversally at the base but with a strong downward curvature. The latter has smaller horns without frontal bosses and without downward curvature, but they are less divergent, being directed backwards as well as laterally. Fossil Syncerus acoelotus from Olduvai [START_REF] Gentry | Fossil Bovidae (Mammalia) of Olduvai Gorge, Tanzania. Part I. 28 halshs-00433315, version 1 -18[END_REF] and Omo [START_REF] Gentry | The Bovidae of the Omo deposits, Ethiopia[END_REF] are as large as the Cape buffalo, but their horn-cores lack the downward curvature, although they are more divergent than those of the forest buffaloes, but they are curved backwards, unlike those of Jamous. Their cross-section is variable (Gentry, 2006, fig. 7) but may be similar to that of Jamous. Nothing in the descriptions of [START_REF] Gentry | Fossil Bovidae (Mammalia) of Olduvai Gorge, Tanzania. Part I. 28 halshs-00433315, version 1 -18[END_REF] and [START_REF] Gentry | The Bovidae of the Omo deposits, Ethiopia[END_REF] suggests that the parieto-occipital area resembled that of Jamous. We have not seen the holotype of S. acoelotus, but its dorsal view (Gentry and Gentry, 1978, pl. 2) shows that, as in modern Syncerus, the horns were close to the occipital, and that the frontal is convex; the best specimen from Omo (National Museum of Ethiopia, Addis Ababa, L-607-1), has the parietal and the very low occipital at right angle to each other, and separated by a sharp nuchal crest; both specimens are therefore very different from Jamous. The middle to late Pleistocene "Pelorovis" antiquus has still larger horns that are even directed forwards at the base before curving backwards. All these buffaloes differ from Jamous by a number of features: 1) their horn-cores are inserted more posteriorly, their anterior border being always more posterior than the orbit; 2) although there is some 20 halshs-00433315, version 1 -18 Nov 2009 intraspecific variation (Gentry, 2006, fig. 7); the horn-core cross-section is more triangular, notably with a posterior keel probably secondarily sharpened; in Jamous the posterior border is rounded; 3) the horn-cores have at least a moderate curvature backwards; the weakest curvature is found in Pelorovis kaisensis [START_REF] Geraads | Geology and Palaeobiology of the Albertine Rift Valley Uganda-Zaire[END_REF], but the very long horn-cores of this poorly known species have a completely different cross section; 4) in connection with 1), the fronto-parietal area is much shortened behind the horn-cores, and the supra-occipital is no longer part of the cranial roof, having been pushed back into the occipital plane. Thus, all African buffaloes are clearly more derived than Jamous in their cranial morphology.

It is instead in some Eurasian bovines that we can find a parieto-occipital morphology reminiscent of Jamous. In Proamphibos from the Tatrot zone of the Upper Siwaliks (Pilgrim, 1939, fig. 30, pl. 5, fig. 3-4), a modest ridge runs between the closely approaching temporal fossae in front of the suture between the parietal and the supra-occipital, but these bones are in the same plane. In Parabos cordieri from the Pliocene of France, the supra-occipital is slightly deflected towards the occipital plane, but there is no transverse ridge. Leptobos is known from both Europe and the Siwaliks; the supra-occipital is oriented as in Jamous, but is much smaller, being both shorter antero-posteriorly between the transverse ridge and the nuchal crest, and narrower because the temporal lines approach closely above the occipital plane (in "Epileptobos" from Java, fusion of these structures produces an occipital "chignon"). The subcircular cross-section of the horn-cores in Leptobos and several cranial characters rule out any close relationship between Leptobos and Jamous, but they are at a similar stage of reorganization of the neurocranium, marked by the beginning of parietal shortening and deflection of the supra-occipital into a more vertical plane, together with thickening of the cranial roof at the limit between these bones. Three incomplete skulls from Sahabi were described as Leptobos syrticus by [START_REF] Petrocchi | I Leptobos di Sahabi[END_REF] and, from the description and figures, photos kindly provided by M. R. Palombo and direct examination of one of Petrocchi's specimens, the parieto-occipital area is indeed similar to that of Leptobos.

similarities with the TM sites (although the latter might include more than one Kobus species), and these similarities may extend to the Antilopini, currently under study. However, a noticeable difference is the disappearance of Saheloryx, a common form at TM. Jamous from KL is quite distinct from the TM Bovini, and the rare Boselaphini of TM went extinct before KB. [START_REF] Fara | Pliocene large-mammal assemblages from northern Chad: sampling and ecological structure[END_REF] have shown that the ecological structure of the faunal assemblages underwent no major changes from KB to KT, and figure 2 of [START_REF] Zazzo | Herbivore paleodiet and paleoenvironmental changes in Chad during the Pliocene using stable isotope ratios of tooth enamel carbonate[END_REF] does not indicate any major change in the C3/C4 proportion in the diet of each bovid tribe (even though, on the whole, there are more grazers in the KT faunal assemblage). What does change, however, is the proportion of the various tribes (as estimated by the number of horn-cores); figure 5 shows that in this respect KB is more different from KL than it is from TM, as though Tchadotragus had replaced the now extinct Saheloryx, before all hippotragines become rare. The KT assemblage differs markedly from the TM-KB-KL ones in that 1) it includes almost no hippotragines, 2) it has a large species of Kobus which is rather common, 3) it has abundant alcelaphines, quite rare in earlier sites, and 4) it has a number of antilopines (most of the "Others" in figure 6) that were less common at TM and quite rare at KB-KL.

In comparison with East Africa, the most noticeable absence in all these sites is that of the Tragelaphini, of which not a single fossil has been found, and the scarcity of Aepyceros, a very successful genus further East. It should be noted that a similar situation is found in the only rich (but significantly younger) Pliocene site of North Africa, Ahl al Oughlam [START_REF] Geraads | Bovidae (Mammalia) du Pliocène final d'Ahl al Oughlam, Casablanca, Maroc[END_REF], which has no Aepyceros and very rare tragelaphines. We may suspect that this is linked with lighter tree cover in central and north-west Africa. Studies in progress on Chadian paleoecology might tell us more about these differences.

However, similarities with North Africa extend beyond the resemblances in tribal composition that reflect ecological conditions, because it is with the Libyan site of Sahabi, rather than with East African ones, that some of the TM, KB and KL bovids compare best, suggesting that some lineages may be endemic to this part of Africa. Indeed, Chadian bovid assemblages have a significant endemic component that suggests that longitudinal exchanges were restricted, at least in the latest Miocene and early Pliocene.

Captions to figures

  Sub-family HIPPOTRAGINAE Sundevall in Retzius and Lovén, 1845 Tribe HIPPOTRAGINI Sundevall in Retzius and Lovén, 1845 4 halshs-00433315, version 1 -18 Nov 2009

  Sub-family indet. Tribe REDUNCINI Knottnerus-Meyer, 1907 Genus KOBUS A. Smith, 1840 KOBUS AMMOLOPHI n.sp. Kobus sp.nov. in Brunet and M.P.F.T., 2000 8 halshs-00433315, version 1 -18 Nov 2009 Holotype-KB3-97-154, a braincase with both horn-cores, and four associated upper molars (Fig. 1E-H; 2F).

FIGURE 1 .

 1 FIGURE 1. A-D: Tchadotragus fanonei; A, distal view of left tibia KB3-97-200; the arrow points to the medially shifted anterior fibular facet; B, KB3-98-146, holotype, lateral view; C-D, KB3-97-200, lateral and anterior views of frontlet; E-H: Kobus ammolophi, KB3-97-154, holotype, in E, dorsal, F, anterior, G, lateral, and H, occipital views. Scale bar equals 20 cm for C-D, 10 cm for A, 15 cm for all others. [planned for page width]

FIGURE 2 .

 2 FIGURE 2. Cross-sections of horn-cores at base, all shown as if from the right side; anterior side to the top of the page, lateral side to the right, except for E. A-C: Tchadotragus fanonei; A, KB3-97-200; B, KB3-96-056; C, KB4-97-151. D, Aepyceros sp., KB3-97-361. E, Jamous kolleensis, KL3-96-013; F-G: Kobus ammolophi; F, KB3-97-154; G, KB4-97-087. Scale bar = 5 cm.[planned for column width]

FIGURE 3 .

 3 FIGURE 3. A, Tchadotragus fanonei, lower tooth-row KB3-97-200. B-C: Kobus ammolophi; B, upper tooth-row P2-M3 KB7-97-098; C, lower tooth-row p4-m3 KB7-97-088. Scale bar equals 4 cm for A, 3 cm for B-C. [planned for column width]

FIGURE 4 .

 4 FIGURE 4. Jamous kolleensis, holotype KL3-96-013, in A, lateral, B, posterior, C, dorsal, D, ventral, and E, oblique postero-dorsal views. Detached horns-cores missing on A and D. Scale bar equals 20 cm. [planned for page width]

FIGURE 5 .

 5 FIGURE 5. Proportion of horn-cores of the various tribes in the Djurab assemblages. "Others" includes Bovini, Antilopini, and Aepyceros. [planned for column width]

halshs-00433315, version 1 -18 Nov 2009

ACKNOWLEDGMENTS

We thank the Chadian Authorities (Ministère de l'Education Nationale, de l'Enseignement Supérieur et de la Recherche, Université de N'djaména, CNAR), the Ministère Français de l'Education Nationale (UFR SFA, Université de Poitiers), Ministère de la Recherche (projet ANR 05-BLAN-0235; CNRS: Départements EDD, SDV and ECLIPSE), Ministère des Affaires Etrangères (DCSUR, Paris and Projet FSP 2005-54 de la Coopération franco-tchadienne, Ambassade de France à N'djaména), the Région Poitou-Charentes, the NSF program RHOI (PI: T. D. White; NSF Award #BCS-0321893), and the Armée Française, MAM and Epervier, for logistical support. We are grateful to many colleagues and friends for their help. We thank also all the other MPFT members who joined us for field missions, and more especially S. Riffaut, X. Valentin for technical support. DG wishes to thank those who granted him access to collections in their care: J. Cuisin, F. Renoult, C. Sagne and P. Tassy (Muséum National d'Histoire Naturelle, Paris), A. Currant (Natural History Museum, London), E. Mbua and M. Muungu (National Museums of Kenya, Nairobi), M.R. Palombo and R. Manni (Dipartimento di Scienze della Terra, Università di Roma), Mamitu Yilma and A. Souron (National Museum of Ethiopia, Addis Ababa). We also thank R. Asher, JVP editor, F. Bibi, and an anonymous reviewer for their critical reading of the manuscript and helpful comments, and D. Reed for polishing the style.

Compared with Kollé, the horn-cores are longer, slightly less divergent, curved backwards and upwards instead of being almost straight, with a more definite antero-dorsal keel, the supra-orbital foramina are less wide apart, the temporal fossae are closer to each other, but the most conspicuous differences are the smaller supra-occipital without a strong transverse ridge, and the fronto-parietal sagittal profile less arched antero-posteriorly. Still, the Sahabi bovine might be the form closest to the Kollé one. All known material of Leptobos syrticus was collected by the Italian parties in 1934-1939, and nothing is known of its stratigraphic origin, but the absence of this species among the material collected by the American-Libyan team [START_REF] Lehmann | Fossil Bovidae (Mammalia) from the Mio-Pliocene of Sahabi, Libya[END_REF] suggests that it might originate from different strata than those worked out by the latter group.

Sub-family HIPPOTRAGINAE Sundevall in Retzius and Lovén, 1845

Tribe HIPPOTRAGINI Sundevall in Retzius and Lovén, 1845 Genus TCHADOTRAGUS Geraads et al., 2008 TCHADOTRAGUS cf. FANONEI Description-KL2-98-135 is a frontlet with virtually complete horn-cores, but so crushed that very few characters are visible. The crushed left pedicle suggests that it was hollowed; the horn-cores are upright, long (about 300 mm along anterior curve), without keels or ridges, transversely compressed, with a backward curvature which regularly increases upwards, and there is no more than a shallow post-cornual fossa. This frontlet is certainly hippotragine. The curvature is distinct from what is typical in Tchadotragus, where there is normally a rather straight terminal portion, but is similar to that of some terminal portions from KB, mentioned above. Specific identification is likely, but more specimens are needed before we can say whether the variability is the same as at KB, or if only one of the KB morphs is present at KL.

Tribe ALCELAPHINI Brooke in Wallace, 1876 KOBUS cf. KOROTORENSIS Geraads et al., 2001 ? Description-KL2-98-101 is a poorly preserved basal fragment, similar to the few specimens from KB described above under this name, but it is not fully certain that it is not merely a weathered specimen of the previous species. We refer to the same species an m3, KL2-98-035 (mid-height length = 22.3 mm), with an ectostylid weaker than at KB, and a few isolated teeth, also from KL2. Some postcranials cannot be identified to species, as both are not very different in size; a complete but crushed metacarpal KL2-98-123 has the following dimensions: Length = 227 mm; min. width of shaft = 20 mm; distal width = 28.7 mm Subfamily ANTILOPINAE Gray, 1821 Tribe ANTILOPINI Gray, 1821 Genus GAZELLA Blainville, 1816 GAZELLA sp.

Description-A calcaneus, KL2-98-136, is of the right size for Antilopini, and must be of a large Gazella (max. length = 60.5 mm).

CONCLUSIONS

The distribution of Bovidae in the Djurab sites is shown in Table 5 (the list for Toros-Menalla is currently being revised).

The two bovid assemblages with the greatest similarities are KB and KL. They probably share Tchadotragus fanonei and the same two species of Kobus. Remains of the other bovids are too incomplete in one or the other site to be certain about their differences. The bovids do not even provide clear evidence that KL is younger than KB. Tchadotragus and Kobus ammolophi are the main positive


Arnaud Soulet
email: arnaud.soulet@univ-tours.fr

Should We Consider On-Demand Analysis in Scale-Free Networks?

Keywords: Decision support system, Analytical queries, On-demand system

Networks are structures used in many fields for which it is necessary to have analytical systems. Often, the size of networks increases over the time so that the connectivity of the nodes follows a power law. This scale-free nature also causes analytical queries to be concentrated on nodes with higher connectivity. Rather than computing the query results for each node in advance, this paper considers an on-demand approach to evaluate its potential gain. To this end, we propose a cost model dedicated to scale-free networks for which we compute the cost for both the offline and on-demand systems. It is reasonable in an on-demand approach to cache part of the results on the fly. We study theoretically and on real-world networks three policies: caching nothing, caching everything and minimizing the total cost. Experiments show that the on-demand approach is relevant if some of the results are cached, especially when the query load is low and the query complexity is reasonable.

Introduction

Networks are complex structures often used to represent information where vertices are entities and edges are their relationships. For example, in citation networks, articles are connected by their references. The Web is a set of pages connected by their links. Social networks connect people through directed ("follower" relationship) or non-directed links ("frienship"). Finally, knowledge graphs connect entities by directed and labeled relations. Most often these networks are characterized by a rapid growth of the number of nodes where the connectivity follows a preferential attachment mechanism leading to nodes that concentrate links -see the Web [START_REF] Barabási | Emergence of scaling in random networks[END_REF], social networks [START_REF] Csányi | Structure of a large social network[END_REF] or knowledge graphs [START_REF] Ding | Characterizing the semantic web on the web[END_REF].

In many fields including bibliometrics [START_REF] Broadus | Toward a definition of "bibliometrics[END_REF] or webometrics [START_REF] Björneborn | Toward a basic framework for webometrics[END_REF], network analytics aims to analyze and extract insights from networks. Many analytical systems produce rich indicators for each node of the network. Typically, Google Scholar offers the same page for each author (with citation number, h-index, and so on). Producing these analyses is a challenge because of the volume of data and the complexity of some indicators. In the era of Big Data, these challenges have mostly been met by resorting to cluster computing frameworks (e.g., MapReduce or Spark) [START_REF] Shi | Clash of the titans: MapReduce vs. Spark for large scale data analytics[END_REF]. Scaling up is not a difficulty for this kind of approach where it is always possible to add computer nodes if the volume of data increases or if the difficulty of the analysis requires it. With this approach, the results once computed are kept and then, when the system is online, the results are returned instantly to the users following their queries. However, since networks evolve rapidly, it is necessary to repeat the costly offline processing regularly. Moreover, with the preferential attachment mechanism, the most popular nodes are also the most accessed. For instance, Yann LeCun's page will be more accessed than those of the PhD students in deep learning publishing their first paper. The undifferentiated processing of nodes thus leads to the generation of analyses that will be computed and stored uselessly because they will never be consulted before the next refresh. It would be possible not to analyze the less popular nodes of the network to reduce costs, or even forget them [START_REF] Kersten | A database system with amnesia[END_REF][START_REF] Davidson | Disposal by design[END_REF]. But, such an approach would be detrimental to the diversity of the analytical system, especially since some rare entities are sometimes the most important (e.g., some little-known entries in a dictionary like DBnary studied in Section 6). In order to reduce costs while preserving the diversity of the network, this paper aims at determining whether it would not be preferable to produce the analyses on-demand.

In this paper, we propose a generic model to understand the impact of different computational and storage strategies for analytical systems in scale-free networks. More specifically, our contributions are as follows:

-We propose a cost model specific to analytical systems in scale-free heterogeneous networks based on types (source entities) and their items (produced entities). -We theoretically compare offline systems with on-demand systems by distinguishing several caching policies (all, nothing, compromise). In particular, we study the utility ratio of cached results. -We evaluate our approach on several real-world graphs showing the interest of using on-demand systems in certain scenarii.

The outline of this paper is as follows. Section 2 reviews some related work about decision support systems. Section 3 introduces basic definitions and the cost model framework. We compute the cost of offline and on-demand systems in Sections 4 and 5 respectively. We apply these models on real-world networks in Section 6 and conclude in Section 7.

Related Work

In the introduction, we have already mentioned approaches based on the MapReduce paradigm to implement distributed and parallel algorithms on clusters. Typically, [START_REF] Liu | Large-scale social network analysis based on MapReduce[END_REF] proposes a method for large-scale social network analysis based on MapReduce. There are generalist frameworks based on MapReduce to analyze data like Apache Pig or Apache Hive [START_REF] Fuad | Processing performance on Apache Pig, Apache Hive and MySQL cluster[END_REF]. In-memory analytics frameworks, such as Apache Spark, that also well-adapted for graph-based analytics [START_REF] Andersen | Evaluating the scaling of graph-algorithms for big data using graphx[END_REF] have also been designed to better handle iterative processes. [START_REF] Lehmann | Distributed semantic analytics using the sansa stack[END_REF] shows how to exploit in-memory frameworks to analyze knowledge graphs. All these approaches process the entirety of the data indiscriminately to produce analyses for each entity. For simplicity, we will refer to this type of approach as offline analytical systems.

Many works in the literature have been interested in analytical queries in the database field (where by nature, the system returns the result of its query on the fly). In particular, they have proposed caching policies and cost models dedicated to this type of queries in relational model [START_REF] Ioannidis | Query optimization[END_REF][START_REF] Shim | Dynamic caching of query results for decision support systems[END_REF] and non-relational models [START_REF] Müller | Aggregates caching in columnar in-memory databases[END_REF][START_REF] Hewasinghage | A cost model for random access queries in document stores[END_REF]. However, the goal of these decision support systems is to be able to answer very diverse queries, whereas in our case we are always interested in the same query applied to a large number of distinct entities. Consequently, most of these works seek to minimize the cost of executing a query while we seek to minimize the cost of a set of queries. More specifically, it is our query set that is unbalanced (few frequent queries, many rare ones) rather than the data associated with a query (which may require the use of histograms [START_REF] Ioannidis | Balancing histogram optimality and practicality for query result size estimation[END_REF]). Moreover, in the following, the cost function of a query is an input to our problem. Another consequence of the variety of queries is that database systems cannot store all the results, contrary to our setup. They therefore implement cache replacement policies [START_REF] Lee | On the existence of a spectrum of policies that subsumes the least recently used (lru) and least frequently used (lfu) policies[END_REF] such as least recent used or least frequently used. In contrast, in this work, we implement a global cache policy that avoids any replacement.

Preliminaries

Scale-free heterogeneous network Let us consider a (heterogeneous) network N = ⟨I, T, τ ⟩ made of a set of items I, a set of types T and a membership relation τ ⊆ I × T . (i, t) ∈ τ means that the item i belongs to the type t. Considering that I ⊆ V and T ⊆ V , we can also consider non-heterogeneous network. The number of types is denoted by s: s = |T |. The degree of the type t ∈ T is the number of items in relation with that t: deg τ (t) = |{i ∈ I : (i, t) ∈ τ }|. The frequency n τ (k) in τ counts how many types t ∈ T are exactly in relation with k items (i.e., its degree deg

τ (t) = k): n τ (k) = |{t ∈ T : deg τ (t) = k}|. The total degree is defined as m τ = ∞ k=1 k × n τ (k) = |τ |.
When the membership relation τ is clear, we omit it: deg(t) refers to deg τ (t), n(t) refers to n τ (t) and so on. A scale-free network is a network whose frequencies n(k) follow a power law (at least asymptotically): n(k) ∼ k -γ with γ > 2. For instance, Figure 1 shows on the left the in-degree distribution of entities in Wikidata (see Section 6 for more details) with the magenta dots. The distribution can be approximated by a power law of exponent γ = 2.058 (see the dash lines).

Analytical system

The end users are interested in an analytical query Q on the network N for different types t. This query Q may lead to complex manipulations of the items of t. For instance, if the types are authors and the items are their publications (with years and citation numbers), a query may compute at the same time the total number of citations, the number of papers per year, the h-index, and so on. An analytical system S Q (or simple S) is a decision support system that efficiently evaluates the analytical query Q on the network N to obtain the result Q(t, N ). In the following, we consider that the network evolves and that a result remains valid for a period ∆.

Cost model Given a type t and a network N , we assume that the cost of the query Q for t in N only depends on its degree deg(t): C(deg(t)) where C is a cost function. In the following, our goal is to evaluate the (average) cost C(S, q, N ) of the system S when it receives q queries during the validity period ∆. Naively, we could think that this average cost of executing q queries is equal to the average query cost repeated q times:

C(S, q, N ) = q • 1 s • t∈T C(deg(t))
This formula is wrong for two reasons: 1) types do not have the same probability of being queried and 2) the system S (whether offline or on-demand) can store query results avoiding the repetition of some queries. For the first point, it is clear that some types will be queried more because of their popularity (as illustrated in the introduction with the Yann LeCun's page). For this purpose, we make the important and realistic assumption that the probability of querying a type t is proportional to its degree deg(t). It is difficult to find data to justify this assumption. Nevertheless, Figure 1 on the right illustrates this phenomenon with the pages of Wikipedia where we see that globally the longest pages are also the most viewed. For the second point, we will see the impact of storing all query results in advance (see offline analytical system in Section 4) or caching a part of the query results on the fly (see on-demand analytical system in Section 5).

Offline Analytical Systems

The principle of an offline system is to compute in advance the queries for all types in order to cache them. When the system is online, it will be enough to return the appropriate result already cached. For the end-user, this approach has the advantage of providing instant answers. Of course, once the validity period ∆ has expired, it will be necessary to invalidate what has been cached to refresh the results. Unfortunately, the cost of this caching is very important since it corresponds exactly to the cost of executing each of the queries:

Property 1 (Offline system cost). Given a network N and a cost function C, the cost of the system S off for q queries is:

C(S off , q, N ) = ∞ k=1 n(k) • C(k)
Due to the lack of space, we omit most of the proofs. For simplicity, Property 1 ignores the parallelization costs which can be significant in some cluster computing architectures. Nonetheless, this cost remains very high because all network types in T are considered without distinction. Unfortunately, a large part of the cached results will never be used. Considering a linear cost C(k) = αk and a scale-free network with exponent γ > 2, we can demonstrate that the cost of the system S off is simply s × α × γ-1 γ-2 as the mean degree is given by (γ -1)/(γ -2) [START_REF] Newman | Power laws, pareto distributions and zipf's law[END_REF].

To evaluate the quality of a system, we calculate the utility ratio (denoted by UR) that is the proportion of the caching cost that was reused. The idea is to evaluate how much of the caching effort was worthwhile. The utility ratio is close to 1 when each caching cost involved a query that was queried again. Conversely, it is close to 0 when what was cached was not queried again resulting in unnecessary caching costs. The following property gives this measure for an offline system: Property 2 (Utility ratio). Given a network N and a cost function C, the utility ratio of the system S off for q queries is:

UR(S off , q, N ) = 1 C(S off , q, N ) • ∞ k=1 1 -1 - k m q • n(k) • C(k)
This property calculates the average probability that a type is queried at least once (i.e., 1 -(1 -k/m) q ) in order to obtain the average number of types queried at least once. Only the costs corresponding to these queries are really useful. It is easy to see that the utility ratio tends towards 1 when the number of queries q becomes large. In contrast, offline systems may not be very relevant in very high velocity networks where the refresh are numerous leading to low query number q.

On-Demand Analytical Systems

The principle of an on-demand system is to evaluate the query for a type t at the time the user requests it. However, it may make sense to cache some frequently requested queries. The challenge is to choose which queries to cache to minimize the overall cost of the query set. To address this problem, we first compute the on-demand system cost (see Section 5.1) and then, we study several caching policies (see Section 5.2).

Cost of on-demand systems

With our cost model, the higher the degree of a type, the more likely it is to be queried. Intuitively, we must therefore determine a degree k cache beyond which we must cache all queries. Below this threshold k cache , the queries will be systematically computed on-demand without any storage. Above this threshold k cache , we check if the result is already cached for returning it directly. If the result is not cached, it is computed and cached. The following property provides the theoretical cost of the system S on : Property 3 system cost). Given a network N and a cost function C, the cost of the system S on for q queries and the degree k cache is:

C(S on , q, N ) = k<k cache q • k m • n(k) • C(k) + k≥k cache 1 -1 - k m q • n(k) • C(k)
This property sums the costs degree by degree by separating them into two parts with respect to the threshold k cache . For degrees less than k cache , the cost for a degree k is the product of the number of performed queries q × k/m × n(k) and the cost of a query C(k). For degrees greater than k cache , only the types queried incur a cost and this cost is unique (because a second query exploits the cache).

It is important to note that the part without cache increases linearly with the number of queries q while the part with cache is upper bounded by k≥k cache n(k) × C(k). To estimate the computation cost C c , these two parts are useful and we have, in the linear case, the following cost per degree: C c (k) = α c k. Conversely, for the storage cost C s , the part without cache has no cost which can be modeled with the following cost per degree:

C s (k) = 0 if k < k cache α s k otherwise
As in the previous section, we compute the utility ratio: Property 4 (Utility ratio). Given a network N and a cost function C, the utility ratio of the system S on for q queries (assuming that q ≫ 1) is:

UR(S on , q, N ) ≈ 1 C(S on , q, N ) • k≥k cache 1 -1 - k m q 1 + q • k m •n(k)•C(k)
It is again necessary to calculate the cost of what is really useful by normalizing it by the cost of what has been cached. Caching is useful if a type of degree greater than degree k cache is queried at least twice (1 time for caching and 1 time for use). The probability of querying a type at least twice is 1 -

1 i=0 q i (1 -k/m) q-i (k/m) i which simplifies if q is large by assuming that (1 -k/m) q-1 ≈ (1 -k/m) q .
As previously, this utility ratio tends towards 1 when the number of queries q becomes large.

Cache policies

Based on the cost model for the on-demand system, we can now consider different policies: caching nothing, caching everything or minimizing the overall cost. Other policies could be considered such as having a maximum cache size.

Let us first consider the extreme cases. The policy of caching nothing (i.e., k cache = +∞) boils down to a linear cost with the number of queries. Therefore, as soon as the number of queries is very large, this strategy has a high cost making it inefficient. On the opposite, the policy of caching everything (i.e., k cache = 0) appears interesting if you have an unlimited amount of storage space. However, the results cached for queries concerning types with a low degree have little chance of being used again. Even if they have a low storage cost, it is a waste of storage.

For this reason, we propose to choose the degree k best that minimizes the total linear cost C t (k) = C c (k) + C s (k) (see above for the definition of C c (k) and C s (k)). Intuitively, the idea is to choose the degree where the costs with cache and without are in equilibrium. In the case of a linear complexity, the below property approximates k best : Property 5 (Theoretical result). Given a network N and the total linear cost function C t (k), the degree k best minimizing the overall cost is given by:

k best ≈ m q • α c • W -(αc+αs)e -αs/αc -1 αc + α c + α s α c
where W is the Lambert W function.

Proof. We give the main steps of the proof. First, we look for the degree k such that the cost without cache is equal to that with cache (see Property 3) by injecting the costs (i.e., C t (k) = α c k for "with cache" and C t (k) = (α c + α s )k for "without cache"):

q • k m • n(k) • α c k = 1 -1 - k m q • n(k) • (α c + α s )k
It is possible to approximate (1 -k/m) q by exp (-q • k/m) as k/m ≪ 1 (that explains the approximation ≈ in the final result). After simplification, we obtain the following equation:

q • k m • α c = 1 -exp - q • k m • (α c + α s )
Solving this equation gives the right-hand side of the result in Property 5.

⊓ ⊔

This property gives a theoretical approximation of the degree k cache which is based on the Lambert W function, quite complex to compute in practice. Therefore, it is simpler to determine k cache by performing a dichotomic search between 0 and k max looking for the minimum cost C(S on , q, N ). Interestingly, this algorithmic approach works for any convex cost function. Furthermore, considering the total linear cost C t (k) and a scale-free network with exponent γ > 2, we simplify the approximation k best by neglecting the Lambert function term and injecting the mean:

k approx = m q • α c + α s α c = s q • γ -1 γ -2 • α c + α s α c

Experimental Study

This experimental study applies our cost models on real-world networks in order to identify the evolution of the total cost and the utility ratio with the number of queries and the complexity of the query. Experimental setting We prepare two knowledge graph benchmarks (denoted by Wikidata and DBnary) based on crowdsourcing projects of Wikimedia Foundation: Wikidata [START_REF] Vrandečić | Wikidata: a free collaborative knowledgebase[END_REF] and DBnary [START_REF] Sérasset | Dbnary: Wiktionary as a lemon-based multilingual lexical resource in rdf[END_REF]. For Wikidata, we used a truthy dump (February 2022) 1 and we filtered each dump to remove literals and external entities whose Uniform Resource Identifier (URI) is not prefixed by http:// www.wikidata.org/. For DBnary, we simply used a dump in turtle format (May 2022) 2 . We also use two existing networks from the SNAP repository: Cell-Cell [START_REF] Zheng | Massively parallel digital transcriptional profiling of single cells[END_REF] and Twitch [START_REF] Rozemberczki | Twitch gamers: a dataset for evaluating proximity preserving and structural role-based node embeddings[END_REF]. Table 1 provides the main characteristics of these four networks. We set the same complexity for storage and computation (e.g., C c (k) =

1 https://dumps.wikimedia.org/other/incr/wikidatawiki/ 2 http://kaiko.getalp.org/static/ontolex/latest/ C s (k) = k 2 for quadratic complexity). For reproducibility, the source code and frequency distributions corresponding to the four networks are available online: https://github.com/asoulet/ida2023ondemand Total cost study We will start by evaluating which strategy is the most parsimonious i.e., with the lowest total cost (computation plus storage). Considering a linear complexity, Figure 2 presents the evolution of the cost with the number of queries for 5 approaches: the offline system, the on-demand system with everything cached (i.e., k cache = 0), nothing cached (i.e., k cache = +∞), best (using k best ) and scale-free approximation (using k approx ). Note that the scales are logarithmic. The offline system (denoted by offline) is obviously independent of the number of queries. Therefore, the more the load increases, the more relevant this approach is. But for the largest datasets, a very high number of queries must be reached, which is unlikely to be achieved due to the data velocity of most networks. Unsurprisingly, the no-cache system (denoted by no cache) is unattractive because its linear cost grows rapidly with the number of queries, exceeding the offline system. The on-demand system caching all queries (denoted by all cache) is not far from te best policy. It is therefore probably the most reasonable policy if the distribution over the whole network is not known. Of course, the on-demand system with cost minimization (denoted by best) is the least expensive approach whatever the number of queries even if its gain is significant for low volumes of queries. Finally, the proposed approximation (denoted by approx) works particularly well since the deviation is not large enough to distinguish the approx curve from the best curve. Now considering 100,000 queries, Figure 3 gives the total cost with different cost function complexity for the same 5 approaches as above. Of course, the higher the complexity of the cost function, the higher the total cost. Typically, there is an order of magnitude increase from constant to linear and from linear to quadratic. The gain of the on-demand system decreases when the complexity is higher. Nevertheless, depending on the network, the on-demand system can remain relevant as it is the case for Cell-Cell with 100,000 queries. As in the previous experiment, the no-cache policy appears to be of little relevance (except for low complexity). Finally, the policy where everything is cached remains competitive with the best and approx policies which, although more subtle, are not significantly better.

Utility ratio study We now study the interest of what has been cached. Considering a linear complexity, Figure 4 presents the evolution of the utility ratio with the number of queries for 4 approaches: the offline system, the on-demand system with three policies: all cache, best and approx. The no-cache policy is Twitch offline all cache best approx Fig. 4. Utility ratio of offline/on-demand systems w.r.t. load of queries not relevant for this study. It clearly appears that the least good approaches are offline and all-cache where a large part of the stored information is never queried. The utility ratio for Cell-Cell is zero up to 10,000 queries because the best solution is to cache nothing. In this experiment, it is visible that the best and approx policies are slightly different. Most often, the best approach stores a little less data explaining a slightly higher utility ratio.

To sum up, the on-demand system is always the most parsimonious if a cache is used. Its gain is stronger when the query load is low and the cost function complexity per query is low. With the best and approx policies, on-the-fly caching is efficient guaranteeing high reuse.

Concluding Remarks

Our study based on a cost model shows the importance of considering an analytical system as a whole. It determines the advantages and weaknesses of different strategies depending on the query complexity and the number of queries: On-demand system interest When the query load is low or network velocity quickly invalidates the cache, on-demand systems are preferred. This avoids performing computation and storing data for types that will never be queried. It should be noted, however, that in our study we did not consider a mechanism for updating the cache of the query result. For example, when a new publication arrives, it is easy to update the different bibliometric indicators without recalculating everything from scratch. Such mechanisms are possible for certain queries, as it is the case with materialized views [START_REF] Gupta | Maintenance of materialized views: Problems, techniques, and applications[END_REF] in the database field.

Cache policy recommendations The use of a cache is absolutely mandatory for on-demand systems in order to store the results of the types with the highest degrees (that are the most queried). When one knows the distribution of the data, it is easy to determine the degree above which query results should be kept. Otherwise, caching everything is still a reasonable policy because types with lower degree have lower storage complexity. However, our study has implicitly focused on a centralized context where caching and retrieval are negligible. In a decentralized context, the situation can be reversed with high storage complexity (due to network communications) while computational costs at the client can be neglected.

Interactivity challenge

The advantage of offline systems is that they guarantee excellent interactivity when their results are used online. For a query on a given type, it is fast to return to the user the result already pre-computed. For ondemand systems, this interactivity is more complicated to guarantee especially for queries with high complexity on a high degree type. We think that two main workarounds can be used. First, systems with low response time (e.g., based on anytime algorithm [START_REF] Soulet | Anytime large-scale analytics of linked open data[END_REF]) should be preferred to those with low execution time. Indeed, it is often possible to propose a partial result quickly that will be refined later. Second, a hybrid strategy could be considered by pre-computing the answers for all types above a certain degree.

Fig. 1 .

 1 Fig. 1. Rationale for our cost model

Fig. 2 .

 2 Fig. 2. Total cost of offline/on-demand systems with different cache policies

Fig. 3 .

 3 Fig. 3. Total cost of offline/on-demand systems w.r.t. cost function complexity

Table 1 .

 1 Main characteristics of networks

	Network Vertices number Edge number Maximum degree Exponent γ
	Wikidata	37,256,044 675,226,687	37,656,116	2.058
	DBnary	38,069,118 198,355,239	19,310,138	2.237
	Cell-Cell	1,018,524	49,471,006	848	2.021
	Twitch	168,116	13,595,116	35,279	2.012

Acknowledgments. This work was partially supported by the grant ANR-21-CE23-0033 ("SELEXINI").